Return list of primes up to n using for loop

I have just picked up learing python and I am trying to create a simple function which accepts an integer and returns a list of all primes from 2 to that integer.

I have created the function but code doesn’t seem to work. I have found solutions only for more efficient (and complex) methodes (like this one Finding prime numbers using list comprehention) for this problem which don’t really help me in finding my mistake.

def list_of_primes(n):
    primes = []
    for y in range (2, n):
        for z in range(2, y):
            if y % x == 0:
                continue
            else:
                primes.append(y)
        primes.sort()
        return primes

What is wrong with the code?

Solution:

There are several errors in your code. Below is a working implementation of your algorithm.

def list_of_primes(n):
    primes = []
    for y in range (2, n):
        for z in range(2, y):
            if y % z == 0:
                break
        else:
            primes.append(y)
    primes.sort()
    return primes

list_of_primes(20)

# [2, 3, 5, 7, 11, 13, 17, 19]

Explanation

  • Indentation is crucial in Python.
  • You need to test if y is divisible by z, not by a variable x which has not been defined.
  • Sort your list and return at the very end, both outside your outer for loop.
  • Use break to skip a number when it is found to be non-prime.
  • Apply your else statement on the inner for loop, not as part of the if / else clause.
Advertisements

How to efficiently find the indices of matching elements in two lists

I am working on two large data sets, and my question is as follows.

Suppose I have two lists:

list1 = [A,B,C,D]

list2 = [B,D,A,G]

How can I efficiently find the matching index, using Python, other than O(n2) searching? The result should look like:

matching_index(list1,list2) -> [(0,2),(1,0),(3,1)]

Solution:

Without duplicates

If your objects are hashable and your lists have no duplicates, you can create an inverse index of the first list and then traverse the second list. This traverses each list only once and thus is O(n).

def find_matching_index(list1, list2):

    inverse_index = { element: index for index, element in enumerate(list1) }

    return [(index, inverse_index[element])
        for index, element in enumerate(list2) if element in inverse_index]

find_matching_index([1,2,3], [3,2,1]) # [(0, 2), (1, 1), (2, 0)]

With duplicates

You can extend the previous solution to account for duplicates. You can keep track of multiple index with a set.

def find_matching_index(list1, list2):

    # Create an inverse index which keys are now sets
    inverse_index = {}

    for index, element in enumerate(list1):

        if element not in inverse_index:
            inverse_index[element] = {index}

        else:
            inverse_index[element].add(index)

    # Traverse the second list    
    matching_index = []

    for index, element in enumerate(list2):

        # We have to create one pair by element in the set of the inverse index
        if element in inverse_index:
            matching_index.extend([(x, index) for x in inverse_index[element]])

    return matching_index

find_matching_index([1, 1, 2], [2, 2, 1]) # [(2, 0), (2, 1), (0, 2), (1, 2)]

Unfortunately, this is no longer O(n). Consider the case where you input [1, 1] and [1, 1], the output is [(0, 0), (0, 1), (1, 0), (1, 1)]. Thus by the size of the output, the worst case is O(n^2).

Although, this solution is still O(n) if there are not duplicates.

Python iterate through array while finding the mean of the top k elements

Suppose I have a Python array a=[3, 5, 2, 7, 5, 3, 6, 8, 4]. My goal is to iterate through this array 3 elements at a time returning the mean of the top 2 of the three elements.

Using the above above, during my iteration step, the first three elements are [3, 5, 2] and the mean of the top 2 elements is 4. The next three elements are [5, 2, 7] and the mean of the top 2 elements is 6. The next three elements are [2, 7, 5] and the mean of the top 2 elements is again 6. …

Hence, the result for the above array would be [4, 6, 6, 6, 5.5, 7, 7].

What is the nicest way to write such a function?

Solution:

Solution

You can use some fancy slicing of your list to manipulate subsets of elements. Simply grab each three element sublist, sort to find the top two elements, and then find the simple average (aka. mean) and add it to a result list.

Code

def get_means(input_list):
    means = []
    for i in xrange(len(input_list)-2):
        three_elements = input_list[i:i+3]
        top_two = sorted(three_elements, reverse=True)[:2]
        means.append(sum(top_two)/2.0)
    return means

Example

print(get_means([3, 5, 2, 7, 5, 3, 6, 8, 4]))
# [4.0, 6.0, 6.0, 6.0, 5.5, 7.0, 7.0]

Maximum distance between two different element in an array

I have a problem where I need to find the maximum distance between two different elements in an array.

For example: given an array 4,6,2,2,6,6,4 , the method should return 5 as the max distance.

I am able to solve the problem using two for loops but it is not an optimized solution. Am trying to optimize it by doing it in a single for loop.

here is my current solution:

int [] A = {4,6,2,2,6,6,4};
int N = A.length;
int result = 0;

for (int i = 0; i < N; i++){
    for (int j = i; j < N; j++) {
        if(A[i] != A[j]){
            result = Math.max(result, j - i);
        }
    }
}

// tried below code but it is not efficient
//      for (int i = 0; i < N; i++){
//          
//          if(A[N-1] != A[i]){
//              result = Math.max(result, N-1-i);
//          }
//      }

System.out.println(result);

How to make this better in terms of time complexity?

Solution:

Simple (not nested) loop is enough, but two cases should be taken into
account: either the best result is

  4,6,2,2,6,6,4
    ^         ^ - moving first

or

  4,6,2,2,6,6,4
  ^         ^   - moving last

for instance: [4, 2, 4, 4, 4] moving first brings the answer, when in case of [4, 4, 4, 2, 4] moving last should be used.

  int first = 0;
  int last = A.length - 1;

  // 1st case: moving "first"
  while (first < last) {
    if (A[first] == A[last])
      first++;
    else
      break;
  }

  int diff1 = last - first;

  first = 0;
  last = A.length - 1;

  // 2nd case: moving "last"
  while (first < last) {
    if (A[first] == A[last])
      last--;
    else
      break;
  }

  int diff2 = last - first;

  // result is the max between two cases
  int result = diff1 > diff2
    ? diff1
    : diff2;

So we have O(N) time complexity.

Edit: Let’s proof that at least one of the indexes is either 0 or length - 1. Let’s do it by contradiction. Suppose we have a solution like

  a, b, c, .... d, e, f, g
        ^ ..... ^  <- solution indexes (no borders)

Items to the left of c must be d, otherwise we can take a or b indexes and have an improved solution. Items to right of d must be c or we can once again push last index to the right and have a better solution. So we have

  d, d, c .... d, c, c, c
        ^ .... ^  <- solution indexes 

Now, since d <> c (c..d is a solution) we can improve the solution into

  d, d, c .... d, c, c, c
        ^ .... ^           <- solution indexes 
  ^       ....          ^  <- better solution

We have a contradiction (the supposed solution is not one – we have a better choice) and that’s why at least one index must be 0 or length - 1.

Now we have 2 scenarions to test:

  a, b, ..... y, z
     ^  ......   ^ <- moving first
  ^  ......   ^    <- moving last

We can combine both conditions into if and have just one loop:

  int result = 0;

  for (int i = 0; i < A.length; ++i)
    if (A[i] != A[A.length - 1] || A[0] != A[A.length - 1 - i]) {
      result = A.length - i - 1;

      break;
    }

Java – Check if array is sorted descendant

I need to check if array was sorted strictly descendant.
I wrote following code

public boolean isSortedDescendant(int [] array){
    if ((array.length == 0) || (array.length == 1)) {
        return true;
    } else {
        for(int i = 0; i < array.length - 1; i++){
            if (array[i] > array[i + 1]) {
                return true;
            }
        }
        return false;
    }
}

But it not working correctly. for

   int[] array2 = {3, 2, 2};

at least. I spend a lot of time for different approaches, but without any luck.

Solution:

You should only return true after checking all the pair of elements:

public boolean isSortedDescendant(int [] array){
    if ((array.length == 0) || (array.length == 1)) {
        return true;
    } else {
        for(int i = 0; i < array.length - 1; i++){
            if (array[i] <= array[i + 1]) {
                return false;
            }
        }
        return true;
    }
}

Finding the odd number out in an array

I am trying to solve a problem where I’m given an array, such as [0, 0, 1, 1, 2, 2, 6, 6, 9, 10, 10] where all numbers are duplicated twice, excluding one number, and I need to return the number that is not duplicated.

I am trying to do it like this:

def findNumber(self, nums):

    if (len(nums) == 1):
        return nums[0]

    nums_copy = nums[:]

    for i in nums:
        nums_copy.remove(i)

        if i not in nums:
            return i
        else:
            nums_copy.remove(i)

However when it reaches the else statement, there is the following error:

ValueError: list.remove(x): x not in list

This is occurring when i is in nums_copy, so I do not understand why this error occurs in this situation?

Solution:

You already nums_copy.remove(i) so you can’t nums_copy.remove(i) again

You could do:

a = [0, 0, 1, 1, 2, 2, 6, 6, 9, 10, 10]

def get_single_instance(array):
  d = {}

  for item in a:
    if item not in d:
      d[item] = 1
    else:
      d[item] += 1

  print d

  for k, v in d.iteritems():
    if v == 1:
      return k

print get_single_instance(a)

Result: 9

Big-O analysis of for loop algorithm

I’m having trouble analyzing the following for loop algorithm:

for (int i = 1; i < n; i = i * C)
    for (int j = 0; j < i; j++)
        Sum[i] += j * Sum[i];

I know that the first line has a complexity of O(logn) (as long as C > 1), but what has me stumped is the second line. I believe I understand the basics of what is happening with it:

For example,

if n=20, the inner loop will do 1+2+4+8+16 “work”.

But I don’t know how to write that out. I’m nearly sure the total work done altogether in the loops is O(n), and that the first line is O(logn), but how do I more concretely specify what the middle line does?

Solution:

i will have values of a form:

C^0, C^1, C^2, ...., C^ log_c(n)

Hence the inner loop will run
C^0 + C^1 + C^2 + ... + C^log_c(n) times. This is a geometric series which sum up to:

enter image description here

So substiture r with C, n with log_c(n) we get:

(1-C^log_c(n)) / (1-C) = (1-n)/(1-C), which is positive for any C > 1 and proportional to n. Hence the complexity is O(n) indeed.

(The formula image is taken from Wikipedia )