Find large number in a list, where all previous numbers are also in the list

user_4430536 0
Viewed 67

I am trying to implement a Yellowstone Integer calculation which suggests that "Every number appears exactly once: this is a permutation of the positive numbers". The formula I have implemented to derive the values is as follows:

import math

yellowstone_list = []
item_list = []
i = 0

while i <= 1000:
    if i <= 3:
        yellowstone_list.append(i)
            
    else:
        j = 1
        inList = 1
        
        while inList == 1:
            minus_1 = math.gcd(j, yellowstone_list[i-1])
            minus_2 = math.gcd(j, yellowstone_list[i-2])
            if minus_1 == 1 and minus_2 > 1:
                if j in yellowstone_list:
                    inList = 1
                else:
                    inList = 0

            j += 1
        
        yellowstone_list.append(j - 1)    
               
    item_list.append(i)

    i += 1

The issue becomes that as i increases, the time taken for the formula to determine the value of j also increases (naturally as i is increasingly further away from the start point of j).

What I would like to do is determine the largest value of j in the yellowstone_list, where all the values of 1 to j are already in the list.

As an example, in the below list, j would be 9, as all the values 0 - 9 are in the list:

yellowstone_list = [0, 1, 2, 3, 4, 9, 8, 15, 14, 5, 6, 25, 12, 35, 16, 7]

Any suggestions on how to implement this in an efficient manner?

python-3.x list python
3 Answers

For the "standalone" problem as stated the algorithm would be:

  1. Sort the list.

  2. Run a counter from 0 while in parallel traversing the list. Once the counter value is unequal to the list element, then you have found one-past the wanted element. Something like the following:

    x=[0, 1, 2, 3, 4, 9, 8, 15, 14, 5, 6, 25, 12, 35, 16, 7]
y=sorted(x)

for i in range(1, len(y)):
    if y[i]!=i:
        print(i-1)
        break

But in your case it appears that the initial list is being built gradually. So each time a number is added to the list, it can be inserted in a sorted manner and can be checked against the previous element and the traversal can start from there for more efficient process.

user_42532290

This is how I would do it:

lst.sort()

for c, i in enumerate(lst):
    if c + 1 < len(lst) and lst[c + 1] != i + 1:
        j = i
        break
    else:
        j = i

Basically, the list is sorted, and then, it loops through each value, checking if the next value is only 1 greater than the current.

user_137391740

After some time to sit down and think about it, and using the suggestions to sort the list, I came up with two solutions:

  • Sorting

I implemented @eugebe Sh.'s solution within the while i < 1000 loop as follows:

    while i <= 1000:

        m = sorted(yellowstone_list)
        for n in range(1, len(m)):
            if m[n]!=n:
                break

        if i == 0:
....
  • In List

I ran an increment to check if the value was in the list using the "in" function, also within the while i < 1000 loop, as follows:

    while i <= 1000:

        while k in yellowstone_list:
            k += 1

        if i == 0:
....

Running both codes 100 times, I got the following:

Sorting: Total: 1:56.403527 seconds, Average: 1.164035 seconds.

In List: Total: 1:14.225230 seconds, Average: 0.742252 seconds.

user_44305360
Related