CODEWITHSUNDEEP
pythonpython-3.x
deega
deega

Reputation: 905

Python / smallest positive integer

I took following codility demo task Write a function:

def solution(A)

that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000]; each element of array A is an integer within the range [−1,000,000..1,000,000].

My Solution

def solution(A):
    # write your code in Python 3.6
    l = len(A)
    B = []
    result = 0
    n = 0
    for i in range(l):
        if A[i] >=1:
            B.append(A[i]) 
    if B ==[]:
        return(1)
    else:    
       B.sort() 
       B = list(dict.fromkeys(B))
       n = len(B)
       for j in range(n-1):
           if B[j+1]>B[j]+1:
                result = (B[j]+1)
       if result != 0:
            return(result)
       else:
            return(B[n-1]+1)

Although I get correct output for all inputs I tried but my score was just 22%. Could somebody please highlight where I am going wrong.

Upvotes: 4

Views: 17200

Answers (12)

Caco
Caco

Reputation: 1654

My solution using sets (not depending on the boundaries for the problem):

def solution(A):
    a_positive = [x for x in A if x > 0]
    set_a_positive = set(a_positive)
    if not set_a_positive:
        return 1
    
    max_a_positive = max(a_positive)
    set_b = set(range(1, max_a_positive + 2))
    return min(set_b ^ set_a_positive)

Upvotes: 0

Hardey
Hardey

Reputation: 1

This is my solution

def solution(A):
    # write your code in Python 3.8.10
    new = set(A)
    max_ = abs(max(A)) #use the absolute here for negative maximum value
    for num in range(1,max_+2):
        if num not in new:
            return num

Upvotes: 0

George m
George m

Reputation: 85

This solution is an easy approach!

def solution(A):
...     A.sort()
...     maxval = A[-1]
...     nextmaxval = A[-2]
...     if maxval < 0:
...             while maxval<= 0:
...                     maxval += 1
...             return maxval
...     else:
...             if nextmaxval + 1 in A:
...                     return maxval +1
...             else:
...                     return nextmaxval + 1

Upvotes: 0

Kraviz
Kraviz

Reputation: 521

I tried the following, and got 100% score

def solution(A):

    A_set = set(A)
    for x in range(10**5 + 1, 1):
        if x not in A_set:
            return x
    else:
        return 10**5 + 1

Upvotes: 0

JohnnyDH
JohnnyDH

Reputation: 2075

def solution(A):
    
    s = set(A)
    for x in range(1,100002):
        if x not in s:
            return x
    pass

And GOT 100%

Upvotes: 3

Ola Ziemińska
Ola Ziemińska

Reputation: 1

My solution (100% acceptance):

def solution(nums):

    nums_set = set()
    for el in nums:
        if el > 0 and el not in nums_set:
            nums_set.add(el)

    sorted_set = sorted(nums_set)

    if len(sorted_set) == 0:
        return 1

    if sorted_set[0] != 1:
        return 1

    for i in range(0, len(sorted_set) - 1, 1):
        diff = sorted_set[i + 1] - sorted_set[i]
        if diff >= 2:
            return sorted_set[i] + 1

    return sorted_set[-1] + 1

Upvotes: 0

Antajo Paulson
Antajo Paulson

Reputation: 584

My Javascript solution. The solution is to sort the array and compare the adjacent elements of the array. Complexity is O(N)

function solution(A) {
// write your code in JavaScript (Node.js 8.9.4)
  A.sort((a, b) => a - b);

  if (A[0] > 1 || A[A.length - 1] < 0 || A.length <= 2) return 1;

  for (let i = 1; i < A.length - 1; ++i) {
    if (A[i] > 0 && (A[i + 1] - A[i]) > 1) {
        return A[i] + 1;
    }
  }

  return A[A.length - 1] + 1;
}

Upvotes: 1

Growyn
Growyn

Reputation: 31

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
    # write your code in Python 3.6
    i = 1;
    B = set(A);
    while True:
        if i not in B:
            return i;
        i+=1;

Upvotes: 1

Vin&#237;cius OA
Vin&#237;cius OA

Reputation: 357

in Codility you must predict correctly others inputs, not only the sample ones and also get a nice performance. I've done this way:

from collections import Counter
def maior_menos_zero(A):
    if A < 0:
        return 1

    else:
        return 1 if A != 1 else 2

def solution(A):
    if len(A) > 1:
        copia = set(A.copy())
        b = max(A)
        c = Counter(A)
        if len(c) == 1:
            return maior_menos_zero(A[0])

        elif 1 not in copia:
            return 1

        else:
            for x in range(1,b+2):
                if x not in copia:
                    return x
    else:
        return maior_menos_zero(A[0])

Got it 100%. If is an array A of len(A) == 1, function maior_menos_zero will be called. Moreover, if it's an len(A) > 1 but its elements are the same (Counter), then function maior_menos_zero will be called again. Finally, if 1 is not in the array, so 1 is the smallest positive integer in it, otherwise 1 is in it and we shall make a for X in range(1,max(A)+2) and check if its elements are in A, futhermore, to save time, the first ocurrence of X not in A is the smallest positive integer.

Upvotes: 0

Eliran Shem Tov
Eliran Shem Tov

Reputation: 628

Python solution with O(N) time complexity and O(N) space complexity:

def solution(A):
    arr = [0] * 1000001
    for a in A:
        if a>0:
            arr[a] = 1
    for i in range(1, 1000000+1):
        if arr[i] == 0:
            return i

My main idea was to:

  1. creat a zero-initialized "buckets" for all the positive possibilities.
  2. Iterate over A. Whenever you meet a positive number, mark it's bucket as visited (1).
  3. Iterate over the "buckets" and return the first zero "bucket".

Upvotes: 9

kotem13
kotem13

Reputation: 71

I think this should be as easy as starting at 1 and checking which number first fails to appear.

def solution(A):
    i = 1
    while i in A:
        i += 1

    return i

You can also consider putting A's elements into a set (for better performance on the search), but I'm not sure that it's worth for this case.

Update: I've been doing some tests with the numbers OP gave (numbers from negative million to positive million and 100000 elements).

100000 elements:
Linear Search: 0.003s
Set Search: 0.017s

1000000 elements (extra test):
Linear Search: 0.8s
Set Search: 2.58s

Upvotes: -1

Errol
Errol

Reputation: 610

Try this, I am assuming the list is not sorted but if it is sorted you can remove the number_list = sorted(number_list) to make it a little bit faster.

def get_smallest_positive_integer(number_list):
    if all(number < 0 for number in number_list) or 1 not in number_list:
        #checks if numbers in list are all negative integers or if 1 is not in list
        return 1
    else:
        try:
            #get the smallest number in missing integers
            number_list = sorted(number_list) # remove if list is already sorted by default
            return min(x for x in range(number_list[0], number_list[-1] + 1) if x not in number_list and x != 0)
        except:
            #if there is no missing number in list get largest number + 1
            return max(number_list) + 1


print(get_smallest_positive_integer(number_list))

input:

number_list = [1,2,3]

output:

>>4

input:

number_list = [-1,-2,-3]

output:

>>1

input:

number_list = [2]

output:

>>1

input:

number_list = [12,1,23,3,4,5,61,7,8,9,11]

output:

>>2

input:

number_list = [-1,3,2,1]

output:

>>4

Upvotes: -1

Related Questions