Solution to Missing-Integer by codility

83 Replies to “Solution to Missing-Integer by codility”

1. Hi!
   Here is a shorter version:

   1 2 3

   def solution(a):     positives = frozenset((value for value in a if value > 0))     return next((i for i in xrange(1, len(a) + 2) if not i in positives), 1)

   it is not clear from the problem description wether the elements of the array must be <= N.
   In case they can take any value within the range it can be changed to:

   1 2 3 4 5 6 7 8

   def solution(a):     positives = frozenset((value for value in a if 0 < value < 2147483648))     if positives:         smallest = min(positives)         start = 0 if smallest < len(a) else smallest         if smallest + len(a) + 1 < 2147483648:             return next((start + i for i in xrange(1, len(positives) + 2) if not start + i in positives), 1)     return 1

   Reply

   • Thanks for sharing you solutions!
     Here, the set should works the same as frozenset, right?

     Reply

   • Hi, I think this solution is wrong. If I pass A = [99999999], I get 100000000. Answer should be 1

     Reply

     • Yes, you are right. The solution has bug. Please try to replace “start = 0 if smallest < len(a) else smallest" with "start = 0".
       Thanks for your good catch!

       Reply

2. Yep, set and frozenset works exact same way, frozenset is immutable.

   Reply

   • Great! THX!

     Reply

3. Hi, here is my solution in PHP 100/100

   1 2 3 4 5 6 7 8 9 10

   function solution($A) {     // write your code in PHP5.3     sort($A);     $min = 1;     foreach($A as $elem)     {         if($elem == $min) $min++;     }     return $min; }

   The same solution ported to Python

   1 2 3 4 5 6 7 8

   def solution(A):     # write your code in Python 2.7     A.sort()     min = 1     for elem in A:         if elem == min:             min+=1     return min

   Reply

   • Hi Ricardo, your solution is right. But the expected worst-case time complexity is O(N). In your solution, you sorted the input array first, which is O(NlogN).
     PS: to post the code, please include your code inside a pre block, instead of code block, like <pre> code </pre>

     Reply

     • Thanks for letting me know it Sheng,
       When I started the exercise I was concerned about sorting the array (as a small developer, Big-O notation never was my biggest concern, until now) but then I got surprised by the result on Codility. They detected a time complexity of O(N).
       Do you know why is that?
       For sort() PHP uses a variation of Quicksort, so shouln’t be O(NlogN) as you stated?
       Thanks

       Reply

       • For the general sorting algorithm in practice (http://en.wikipedia.org/wiki/Sorting_algorithm), the bese worst-case complexity is O(NlogN).
         logN is small even with a big N. And Codility’s detection is not exactly accurate, and gave you a wrong estimation here.
         Thanks for visiting my site! And enjoy coding and photography!

         Reply

   • By the way, your photoes are amazing! I love them!

     Reply

     • Thanks, I love photography for as long as I can remember 😀

       Reply

4. Here is my solution, following “Pigeonhole principle”:

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

   class Solution {     public int solution(int[] A) {         int N = A.length+1;         boolean[] numPresent = new boolean[N + 1];         for (int i = 1; i < N; i++) {             if (A[i-1]  N) {                 continue;             }             if (!numPresent[A[i-1]]) {                 numPresent[A[i-1]] = true;             }         }         int smallest = 1;         for (int j = 1; j < numPresent.length; j++) {             if (!numPresent[j]) {                 smallest = j;                 break;             }             smallest++;         }         return smallest;     } }

   Result:
   https://codility.com/demo/results/demoMSXU28-G6F/

   Reply

5. Hi,
   Thanks for posting your solution. I learned something new from this one. Just wanted to share an opinion: I know that complexity is expressed based on the worst case scenario, but statistically I think that a solution that sorts the array first will almost always be faster. And that’s of course if we assume that the input is an array of random (or seemingly random) numbers, not someone deliberately creating worst case scenarios.
   So if we do something like this:
   1. sort the array,
   2. go through the sorted array (ignoring negative values)
   2.1. check if the first positive element is greater than 1, i which case just return 1, which leaves just the sort complexity O(logN), and that’s most cases when dealing with random input
   2.2. otherwise look for the first gap (between positive numbers), which, in the case of random input will most probably be very early in the array, giving O(logN) + O(small fraction of N)
   So if we were to solve a real world problem, we would probably inspect the input statistically (maybe even ad-hoc, using intuition) and then choose the solution that works the best for the specific use. The worst case O(logN)+O(N) would just be a very very rare occurrence.
   Best Regards
   🙂

   Reply

   • Thanks for your discussion! However, the average performance of the best practical sorting algorithms is O(NlogN), not O(logN). Therefore, your solution does NOT fit the requirements.

     Reply

6. Bad solution (Pascal)

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

   function solution(A: array of longint; N: longint): longint; var     i,missing:longint; begin    missing:=1;    i:=0;     while(i<=high(a)) do     begin         if a[i]=missing then         begin             missing:=missing+1;             i:=0;         end         else         begin             i:=i+1;         end;     end;     solution:=missing; end;

   Reply

   • It is bad because of the time complexity:
     O(N**2)
     It got a 100% for Correctness and a 25% for Performance. So it’s a fail

     Reply

7. Also a bad Pascal solution (same time complexity O(N**2)) score : 100% and 50%
   (now sorting the array before doing the calculations)

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

   Procedure QSort(var A : Array of longint; left : longint; right : longint); Var pivot, l_ptr, r_ptr : longint; Begin l_ptr := left; r_ptr := right; pivot := A[left]; While (left < right) do   Begin    While ((A[right] >= pivot) AND (left < right)) do     right := right - 1;    If (left <> right) then     Begin      A[left] := A[right];      left := left + 1;     End;    While ((A[left] <= pivot) AND (left < right)) do     left := left + 1;    If (left <> right) then     Begin      A[right] := A[left];      right := right - 1;     End;   End; A[left] := pivot; pivot := left; left := l_ptr; right := r_ptr; If (left < pivot) then   QSort(A, left, pivot-1); If (right > pivot) then   QSort(A, pivot+1, right); End; function solution(A: array of longint; N: longint): longint; var     i,minim:longint; begin     QSort(A, 0, N-1);     minim := 1;     for i:=0 to High(a) do         if a[i] = minim then minim:=minim+1;     solution:=minim; end;

   Reply

   • I sincerely appreciate your sharing and involvement. However, to keep the comunity clear, please only post the good solutions. Sorry for that.

     Reply

8. Ruby 100%

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

   def solution(a)     b=Array.new(a.count+1,0)     smallest_int=a.count+1     a.each do |i|         b[i]=1 if (i>0 && i<smallest_int)     end     b.count.times do |i|         i+=1         if b[i] == 0             smallest_int=i             return smallest_int         end     end     return smallest_int end

   Reply

   • Ruby

     1 2 3 4

     def solution(a)   missing = (1..a.count+1).to_a - a   missing[0] end

     Reply

     • Although your solution is valid (tested in ruby console):

       It’ll not work on the Codility challenge because as of Ruby 1.9.0, String#s are no longer Enumerable. You can’t simply iterate over a String or convert it to an Array

       Reply

9. 100% in JS https://codility.com/demo/results/demoWN6DHU-JVT/

   1 2 3 4 5 6 7 8 9 10 11 12 13 14

   function solution(A) {     var onlyPositiveInt = [];     for (var i =0; i < A.length; i++){         if (A[i] > 0 ){             onlyPositiveInt[A[i]] = true;         }     }     for (i = 1; i <= onlyPositiveInt.length; i++){         if (!onlyPositiveInt[i]){             return i;         }     }     return 1; }

   Reply

   • No you didn’t, I just test your solution verbatim and it doesn’t work.

     Reply

     • I also tried minutes ago. It does work.

       Reply

10. – add up the total of the array (s) and count the number of elements. (n)
    – for the full array 1..n+1 the sum would be (1+n+1)*(n+1)/2 i.e. there are n/2 pairs of numbers summing to 1+ (n+1)
    – therefore the difference between the expected sum (including the missing element) and the actual calculated sum s is the missing value
    – works in O(n)

    Reply

    • Yes, logically it is right. But it may lead to overflow, which makes the result unreliable.

      Reply

    • Are you sure this is ok if the numbers in array are totally random and can be repeating ?

      Reply

      • It works if and only if the numbers are unique and in range of 1 to N + 1. I was wrong.

        Reply

11. This is my python solution for 100%:

    1 2	def solution(a):     return min(set(range(1, len(a) + 2)).difference(set(a)))

    Reply

    • Assuming the hash function is perfect (which is next to being real), the solution is a good exmaple of hash set.
      Thanks!

      Reply

    • i am learning python. can you please explain how this works?

      Reply

      • set(range(1, len(a) + 2)) is the set of all elements plus one possible missing integer.
        set(a) is the set of all candidates, after dedup.
        You could Google and find all these build-in functions.

        Reply

    • Hi Ben,

      I’m new to python programming.

      Can you explain to me how you came up with your answer?

      Reply

    • Simply genius

      Reply

12. Here my solution in Java 100%, a little bit verbose but it works:

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

    public int solution(int[] A) {         HashSet<Integer> positives = new HashSet<>(); // to add just positives         int max = 1, length = A.length;         for (int i =0; i < length; ++i) {              int current = A[i];             if (current < 0 ) {                 continue;             } else {                  positives.add(current);                 if( max <= current) {                     max = current;                 }             }         }         max = Math.max(max, length); // taking into account arrays with random elements         for(int i = 1; i <= max ; ++i) {              if(!positives.contains(i)) {                  return i;             }         }         return length + 1; // array is complete     }

    Here’s the link:
    https://codility.com/demo/results/demoA3WP3K-ZCA/

    Reply

    • How come every solution checks from the 1..N range?
      Shouldn’t an array containing:
      A = [3, 4, 6];
      return 5 instead of 1?
      Also in the problem statement it’s not clear what value to return if the array is complete. How did you guess what they required?

      Reply

      • The problem statement: returns the minimal positive integer (greater than 0) that does not occur in A.

        Reply

    • Hi, I came to this answer 5 years later!
      I change this line:
      max = Math.max(max, length); // taking into account arrays with random elements

      with this:
      max = Math.max(max, positives.size());

      Let me know your opinion.
      Best Regards

      Reply

13. 1 2 3 4 5 6 7 8 9 10 11 12 13

    function solution(A) {     A = A.filter(function(current){return current >= 0;}).sort(function(a,b){return a-b;});     var min = 0;     for(var i = 0; i < A.length; i += 1) {         if((A[i] - min) > 1) {             return min+1;         }         if ((A[i] - min) === 1) {             min = A[i];         }     }     return min+1; }

    Another JS solution this one works 100% 🙂

    Reply

    • Awesome! However, the variable name “min” is a little bit misleading. It is actually the trying prober for the result.

      Reply

14. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

    #include int solution(vector<int> &A) {     // write your code in C++11     int counter=1;     std::list<int> intList (A.begin(),A.end());     intList.sort();     intList.unique();      for (std::list<int>::iterator it=intList.begin() ; it != intList.end(); ++it)      {         if(*it<1)         continue;         if(*it!=counter)         return counter;         else         counter++;       }     return counter; }

    Reply

15. Solution in C#:

    1 2 3 4 5 6 7 8

    List myList = A.Distinct().Where(i => i > 0).ToList(); myList.Sort(); for (int i = 0; i < myList.Count; i++) {     if (myList[i] == i + 1) continue;     else return i + 1; } return  myList.Count()+1;

    Reply

16. I don’t understand limiting the size of the occurrence array to N elements.
    According to the problem on Codility,
    N is an integer within the range [1..100,000];
    each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
    So A might be [2147483647] for example where N=1 and then the A[item..] references would be out of range.
    Have I misunderstood the question?

    Reply

    • It’s pigeonhole principle. With N integers, the minimal missing *positive* integer must be in the range of [1, N + 1] (both ends inclusive).

      Reply

17. Something I dont get is, wouldn’t doing 2 for loops end up being O(2N)?

    Reply

    • Big O is used to measure the order of complexity. O(2N) means exactly the same thing as O(N).

      Reply

18. Here is my solution in Python, 100% in both correctness and performance

    1 2 3 4 5 6 7 8 9 10 11

    def solution(A):     # first sort the array to get the numbers in sequence     A = sorted(A)     # the minimum positive integer that may not be found will be 1     min_not_found = 1     # loop through the array     for element in A:         # if the current element is the min_not_found number, move to next number         if element == min_not_found:             min_not_found += 1     return min_not_found

    Reply

    • Expected worst-case time complexity is O(N), while yours is O(NlogN) because of the sorting.

      Reply

19. what if I don’t know pigeonhole principle? O(N) time with O(1) space:

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

    #include <vector> #include <algorithm> using namespace std; class SolutionFirstMissingPositive { public:     int firstMissingPositive(vector<int> A) {         int len = A.size();         if (0 == len)return 1;         int cnt = 0;         for (int i = 0; i < len; ++i)         {             if (A[i] - 1 != i)             {                 while (A[i] > 0 && A[i] <= len && A[A[i] - 1] != A[i])                     std::swap(A[i], A[A[i] - 1]);             }         }         for (int i = 1; i <= len; ++i)             if (i != A[i - 1])                 return i;         return len + 1;     } };

    Reply

    • reading my blog 🙂 just kidding

      Reply

20. My solution in ruby

    1 2 3 4

    def solution(a)   missing = (1..a.count+1).to_a - a   missing[0] end

    Reply

21. My solution in javascript

    1 2 3 4 5 6 7 8 9 10 11

    const solution = A => {     const array = [...new Set(A)].filter((v, i) => v > 0).sort((a,b) => a-b);     let value = array.length+1;     for (i = 0; i < array.length; i++) {         if(array[i] !== i+1){             value = i+1;             break;         }     }     return value; }

    Reply

22. in case you need code in JS, ES6.
    A.sort((a,b) => Math.abs(a) - Math.abs(b)).reduce((res, val) => { val === res ? res++ : res; return res; }, 1))

    Reply

23. Here my solution in Java. It works but the time complexity is: O(N) or O(N * log(N))

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

    class Solution {     public int solution(int[] A) {         // write your code in Java SE 8         boolean[] B = new boolean[A.length];         int i =0;         for(i=0; i<A.length;i++){             if((A[i]>0) && (A[i]<=A.length) && (B[A[i]-1] == false))                 B[A[i]-1] = true;         }         for(i=0; i< B.length;i++){             if(B[i]==false)                 return i+1;         }         if(i==B.length)             return i+1;         else             return 1;     } }

    Reply

24. My solution using Google go language

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

    package main import "fmt" func solution(A []int) int {     positives := make(map[int]bool, len(A)+1)     for _, v := range A {         if v > 0 {             positives[v] = true         }     }     smallest := 1     for {         if positives[smallest] == false {             return smallest         }         smallest++     } } func main() {     arr := []int{2, 3, -4, -6, 1, 4, 7, 5, 6}     fmt.Println(solution(arr)) //prints 8     arr2 := []int{1, 3, 6, 4, 1, 2}     fmt.Println(solution(arr2)) //prints 5     arr3 := []int{1, 2, 3}     fmt.Println(solution(arr3)) //prints 4     arr4 := []int{-1, -3}     fmt.Println(solution(arr4)) //prints 1     arr5 := []int{3, 4, 6}     fmt.Println(solution(arr5)) //prints 1; Not sure if this is correct. Should it return 5? Your comment please }

    Reply

25. My solution using C++ – 100%

    1 2 3 4 5 6 7 8 9 10 11 12 13 14

    #include <algorithm> int solution(vector<int> &A) {     sort(A.begin(), A.end());     auto maximum = *max_element(A.begin(), A.end());     auto result = 1;     auto finded = A.begin();     for(;result <= maximum; ++result)     {         finded = find(finded, A.end(),result);         if(finded==A.end())             return result;     }     return result; }

    Reply

26. solution in Ruby for 100%
    but
    Detected time complexity:
    O(N) or O(N * log(N))

    1 2 3

    def solution(a)   ((1..a.size).to_a - a).first || a.max+1 end

    Reply

27. 1 2 3 4 5 6 7 8 9

    def solution(A):     a=0     for i in range(1,len(A)+2):         if i in A:             pass         else:             a+=i             break     return a

    Reply

28. 1 2 3 4 5 6 7 8 9 10 11 12

    public int solution(int[] A) {     int number =1;     int size = A.length;     HashSet<Integer> missingInteger = new HashSet<Integer>();     for(int i=0; i<size; i++){         missingInteger.add(A[i]);     }     while(missingInteger.contains(number)){         number++;     }     return number; }

    Reply

29. My Java Solution 100%

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

    public int solution(int[] A) {         int len = A.length;         int[] occurrence = new int[len];         int negativeCnt = 0;         for (int a : A) {             if (a < 1 || a > len) {                 negativeCnt++;                 continue;             }             occurrence[a - 1] = 1;         }         if (negativeCnt == len) {             return 1;         }         for (int i = 0; i < len; i++) {             if (occurrence[i] == 0) {                 return i + 1;             }         }         return len + 1;     }

    Reply

30. PHP 100%

    1 2 3 4 5 6 7 8 9 10 11

    function solution($A) {     $a = array();     foreach($A as $k=>$v){         if($v > 0 && $v < 100001)         $a[$v] = true;     }     if(count($a)==0)return 1;     for($i = 1; $i <= 100001; $i++){         if(!isset($a[$i]))return $i;     } }

    Reply

31. Javascript 100% (however, both this and my previous PHP version even though scoring 100% show Detected time complexity: O(N) or O(N * log(N)) SO next I’m going to study that pidgeonhole principal.

    1 2 3 4 5 6 7

    function solution(A) {     let a = new Set(A);     for(i=1;i<=100001;i++){         if(!a.has(i))return i;     }     return 1; }

    Reply

32. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

    function solution(A) {     // write your code in JavaScript (Node.js 8.9.4)     let store = [];     for(let i =0;i<A.length;i++){         if(A[i]<0) continue;         if(store[A[i]]==undefined) store[A[i]]=A[i];     }     //console.log(store);     for(let i=1;i<store.length;i++){         if(store[i]==undefined) return i;     }     if(store.length===0) return 1;     else return store[store.length-1]+1      }

    Reply

33. 1 2 3 4 5 6 7 8 9 10 11 12 13 14

    def solution(A):     A.sort()     highest = A[-1]     if 1 not in A:         return 1     if highest > 0:         for i in  range(0, len(A)-1):             if A[i] < 1:                 continue             elif A[i]+1 !=  A[i+1] and A[i] != A[i+1]:                 return A[i]+1     elif highest <= 0:         return 1         return highest+1

    Reply

34. If someone is looking for a java solution can try it (100% in both correctness and performance)

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

    public int solution(int[] A) {                 boolean []  buffer = new boolean[A.length + 1];                  for(int elem : A) {             if(elem > 0 && elem < buffer.length) {                 buffer[elem - 1] = true;             }         }                  boolean found = false;         int result = 0;         for(int i = 0; !found && i < buffer.length; i++) {             result = i + 1;             found = !buffer[i];         }         return result;     }

    Reply

35. 1 2 3 4 5

    def solution(A):     a_set = set(A)     for i in range(1, 1000002):         if i not in a_set:             return i

    This is one easy way based on the edge cases given

    Reply

36. This post still comes up so I’ll put my JavaScript solution for keepsake 🙂

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

    function solution(A) {     // write your code in JavaScript (Node.js 8.9.4)     const f = [...A].filter(n => n > 0);          const l = f.length;          if(!f.length) return 1;          const g = f.reduce((a,c) => {         a[c] = true;         return a;     },{});          for ( i = 1; i <= l; i++) {         if(!g[i]) return i     }          return Math.max.apply(null, f) + 1; }

    Scores 100% on Task score – Correctness – Performance

    Reply

37. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

    def solution(A):     counter = {"negative+0": False, "positive": False}     for hits in range(0, len(A)):         if A[hits] > 0:             counter[A[hits]] = 1             counter["positive"] = True         if not counter["negative+0"]:             if A[hits] < 0:                 counter["negative+0"] = True     if (counter["negative+0"] == True) & (counter["positive"] == False):         return 1     if counter["positive"] == 1:         del counter["negative+0"]         del counter["positive"]         if 1 in counter:             print(counter)             return sum(range(1, len(counter) + 2)) - sum(counter)         else:             return min(counter) - 1     #A = [1,3,6,4,1,2] #A = [1,2,3] #A = [-1, -3] A = [3,4,57,6] print(solution(A))

    Reply

38. Hi, how performance of function set() does look like? Is it much faster compare to single for loop with list or dict as a help?

    1 2 3 4 5 6

    def solution(A):     counter = {}     for hits in A:         if hits > 0:             counter[hits] = 1         return counter

    Reply

    • I cannot see why it’s working. The problem asks for a single integer, while your code returns a dictionary.

      Reply

39. 100% on codility but time complexity O(N) or O(N*log(N))

    1 2 3 4 5 6 7 8 9 10 11 12 13 14

    def solution(A):     B=[0]*(max(A)+1)       if max(A)<1:         return(1)       for x in range(len(A)):         if A[x]>0:             B[A[x]-1]=1     print(B)       for x in range(len(B)):         if B[x]==0:             return(x+1)

    Not heard of the pigeon hole but now going to look into it.

    Reply

40. 1 2 3 4 5 6 7 8 9 10

    def solution(A):     # write your code in Python 3.6     array_to_set = set(A)     if max(list(array_to_set)) < 0:         return 1     else:         for num in list(range(1,max(list(array_to_set))+2)):             if num not in array_to_set:                 return num         #pass

    Reply

41. My solution. I thought the time complexity should be O(N), Why it says it is O(N**2)?

    1 2 3 4 5

    def solution(A):     for item in range(len(A)):         if item + 1 not in A:             return item + 1     return item + 2

    Reply

    • Because of the not in operation.

      Reply

42. This hasn’t been updated in a while… just FYI in case you were confused reading the solution:
    The question has changed and now in the array there aren’t only integers between 1 and N allowed, it’s *any* N integers between 1 and 100000.
    The pidginhole therefore won’t work anymore.

    But I liked reading about your approach.
    If you can provide a solution for the new problem NOT using sort (which I do) I’d be grateful to see it. 🙂

    Reply

    • It’s still working well: https://app.codility.com/demo/results/training244KA2-MMX/

      pidginhole 🙂 You said it, and you should know it.

      Reply

43. 100% solution using Swift – I do not fully understand the Pinghole principle but it works!

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

    public func solution(_ A : inout [Int]) -> Int {     // write your code in Swift 4.2.1 (Linux)          //using Pinghole principle          //get N+1     let countPlusOne = A.count + 1     //create dummy array     var occurence = Array(repeating: false, count: countPlusOne)     for i in A {         if i < 1 {continue} //ignore negatives         if i > countPlusOne {continue} //ignore N+1         occurence[i-1] = true     }     //find the missing minimal     for i in 0...countPlusOne {         if occurence[i] == false{             return i + 1         }     }          return -1   }

    Reply

44. My solution in Python:

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

    def solution(A):     w=min(A)     x=max(A)     y=len(A)     z=A.count(1)     A.sort()     if z==0:         return 1     elif y==1:         return 2     else:         for i in range(1,x+1,1):             if i not in A:                 return i             elif i==A[y-1]:                 return A[y-1]+1             else:                 pass

    Reply

45. Solution in Python 100% :-

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

    def solution(A):     n = len(A)     x = 0     for i in range(n):         if A[i] == 1:             x = 1             break     if x == 0:         return (1)       for i in range(n):         if A[i] <= 0 or A[i] > n:             A[i] = 1                  for i in range(n):         A[(A[i] - 1) % n] += n       for i in range(n):         if A[i] <= n:             return(i+1)     return (n+1)   list = [7,2,4,1,6,3,5,8] print(solution(list))

    Reply

46. This is my c++ solution with 100% performance and correctness

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

    int solution(vector &A) {     // write your code in C++14 (g++ 6.2.0)     sort(A.begin(),A.end());     int index = -1 , StartNumber = -1;     for(uint32_t i = 0 ; i <A>= 0)         {             index = i;             break;         }     }       if (index == -1)         return 1 ;       StartNumber = A[index];       if (StartNumber > 1)             return 1 ;       for (uint32_t i = index + 1 ; i < A.size(); i++)     {         if (A[i] == StartNumber + 1)         {             StartNumber++;         }else if (A[i] == StartNumber){             continue;         }else {             break;         }     }     return StartNumber +1; }

    Reply

47. 100% on correctness and performance. Detected Time Complexity – O(N) or O(NlogN). I’ve explained my code with comments.

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

    def solution(A):     # sort the list     A.sort()     # append index of non-positive integers in indicies     indicies = []     for index, int_val in enumerate(A):         if int_val <= 0:             indicies.append(index)     # check if a non-positive integer is present in array A     # if present, use the last occurrence of that non-positive     # integer to slice array A     if min(A) <= 0:         A = A[indicies[-1]+1:]     # now check for extreme case in which the function returns 1     if len(A) == 0 or min(A) != 1:         return 1     # after eliminating different cases check for the case,     # where array starts with 1 and only positive integers are present     # lag array A by removing last integer and add 0 to the start     B = [0] + A[:-1]     # perform element wise subtraction of A from B,     C = list(map(lambda a,b: a-b, A,B))     # if the sequence is complete and no missing integer is found     # the function returns the last integer in array A plus 1     if 0 <= max(C) <= 1:         return A[-1]+1     # if the sequence is incomplete and there is an instance of     # missing integer, find the first instance where difference     # between current and previous element > 1 and return that     # value of integer at that index-1 plus 1     else:         for index, int_val in enumerate(C):             if int_val > 1:                 return A[index-1] + 1

    Reply

48. 1 2 3 4 5 6 7 8

    def missingnum(a):     st=min(a)     en=max(a)     b=set(range(1,en+2))     if (en<1 or st>1) :         return 1     else:         return min(b-set(a))

    Reply