Find the smallest positive integer that does not occur in a given sequence

Question

I was trying to solve a problem in Codility provided below    Write a function   class Solution   public int solution int   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    Assume that   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   Complexity   expected worst-case time complexity is O N   expected worst-case space complexity is O N   not counting the storage required for input arguments    I write the solution below which gives a low performance  however  I can t see the bug    public static int solution int   A             Set lt Integer gt  set   new TreeSet lt  gt              for  int a   A                set add a                      int N   set size             int   C   new int N            int index   0           for  int a   set                C index      a                     for  int i   0  i  lt  N  i                   if  C i   gt  0  amp  amp  C i   lt   N                    C i    0                                   for  int i   0  i  lt  N  i                   if  C i     0                    return  i   1                                    return  N   1           The score is provided here      I will keep investigating myself  but please inform me if you can see better

User · Accepted Answer

If the expected running time should be linear, you can't use a TreeSet, which sorts the input and therefore requires O(NlogN). Therefore you should use a HashSet, which requires O(N) time to add N elements.

Besides, you don't need 4 loops. It's sufficient to add all the positive input elements to a HashSet (first loop) and then find the first positive integer not in that Set (second loop).

int N = A.length;
Set<Integer> set = new HashSet<>();
for (int a : A) {
    if (a > 0) {
        set.add(a);
    }
}
for (int i = 1; i <= N + 1; i++) {
    if (!set.contains(i)) {
        return i;
    }
}

User · Answer

C  solution      public int solution int   A                int result   1              write your code in Java SE 8         foreach int num in A                        if  num    result                 result                 while  A Contains result                   result                       return result

User · Answer

Here is a simple and fast code in PHP    Task Score   100  Correctness  100  Performance  100  Detected time complexity  O N  or O N   log N     function solution  A          x   1       sort  A        foreach  A as  i            if  i  lt  0  continue           if  x  lt   i  return  x           else  x    i 1               return  x      Performance tests

User · Answer

package Consumer    import java util Arrays  import java util List  import java util stream Collectors   public class codility   public static void main String a                  int   A    1 9 8 7 6 4 2 3           int B     -7 -5 -9           int C     1 -2 3           int D     1 2 3           int E      -1           int F      0           int G      -1000000           System out println getSmall F              public static int getSmall int   A                int j 0          if A length  lt  1    A length  gt  100000  return -1          List lt Integer gt  intList   Arrays stream A  boxed   sorted   collect Collectors toList              if intList get 0   lt  -1000000    intList get intList size  -1   gt  1000000  return -1           if intList get intList size  -1   lt  0  return 1          int count 0                    for int i 1  i lt  intList size   i                            if  intList contains i  return i               count                        if count  intList size    return   count          return -1

User · Answer

Here s my solution in C    It got a 100  score  100  correctness  100  performance   after multiple tries      It relies on the simple principle of comparing its values to their corresponding index  after a little preprocessing such as sorting   I agree that your solution is doing too much  You don t need four loops   The steps of my solution are basically    Sort and remove any duplicates  There are two possible methods here  the first one utilizing std  sort  std  unique  and erase  while the second one takes advantage of std  set and the fact that a set sorts itself and disallows duplicates Handle edge cases  of which there are quite a few  I missed these initially  causing my score to be quite low at first   The three edge cases are    All ints in the original array were negative All ints in the original array were positive and greater than 1 The original array had only 1 element in it  For every element  check if its value    its index 1  The first element for which this is true is where the smallest missing positive integer is  I e  if vec at i     i 1  then vec at i-1  1 is the smallest missing positive integer  If vec at i     i 1 is false for all elements in the array  then there are no  gaps  in the array s sequence  and the smallest positive int is simply vec back   1  the 4th edge case if you will     And the code   int solution vector lt int gt  amp  rawVec          Sort and remove duplicates  Method 1     std  sort rawVec begin    rawVec end         rawVec erase std  unique rawVec begin    rawVec end     rawVec end            Sort and remove duplicates  Method 2        std  set lt int gt  s rawVec begin    rawVec end            rawVec assign s begin    s end            Remove all ints  lt  1     vector lt int gt  vec      vec reserve rawVec size         for const auto amp  el   rawVec                if el gt 0              vec push back el                Edge case  All ints were  lt  1 or all ints were  gt  1     if vec size    0 or vec at 0     1          return 1         Edge case  vector contains only one element     if vec size    1          return  vec at 0   1   1   2        for int i 0  i lt vec size      i                if vec at i     i 1              return vec at i-1  1            return vec back   1

User · Answer

This solution runs in O N  complexity and all the corner cases are covered      public int solution int   A            Arrays sort A             find the first positive integer         int i   0  len   A length          while  i  lt  len  amp  amp  A i     lt  1            --i             Check if minimum value 1 is present         if  A i     1              return 1             Find the missing element         int j   1          while  i  lt  len - 1                if  j    A i   1   i                else if    j    A i   1                   return j                        If we have reached the end of array  then increment out value         if  j    A len - 1               j            return j

User · Answer

My solution having 100  result in codility with Swift 4   func solution   A    Int   - gt  Int       let positive   A filter    0  gt  0   sorted       var x   1     for val in positive          if x  lt  val                return x                   x   val   1           return x

User · Answer

My solution on Ruby  def solution a    p        b   1   a each do  n      p n    n     b   n if n  gt  b   end    nb   b    b-1  downto 1  do  n      unless p n        nb   n       break     end   end      nb    b    b 1   nb end  puts solution  1 3 5 4 1 2 6   puts solution  1 3 6 4 1 2 5   puts solution  1 2 3

User · Answer

you can also use imports  for example     import java util        you can write to stdout for debugging purposes  e g     System out println  this is a debug message     class Solution       public int solution int   A        int size A length      int min A 0       for int i 1 i lt  size i             boolean found false          for int j 0 j lt size j                 if A j  lt min  min A j                if i  A j                    found true                                      if found  false                   return i                                if min lt 0  return 1           return size 1

User · Answer

In Kotlin with  100 score Detected time complexity  O N  or O N   log N    fun solution A  IntArray   Int       var min   1     val b   A sortedArray       for  i in 0 until b size            if  b i     min                min                       return min

User · Answer

Without sorting or extra memory  Time Complexity  O N    public int solution int   A            for  int i   0  i  lt  A length  i                  if  A i   lt   0    A i   gt   A length  continue              int cur   A i   point              while  cur  gt  0  amp  amp  cur  lt   A length  amp  amp  A cur - 1     cur                    point   A cur - 1                   A cur - 1    cur                  cur   point                  if  cur  lt  0    cur  gt   A length  break                                  for  int i   0  i  lt  A length  i                  if  A i     i 1  return i 1                    return A length   1

User · Answer

Objective-C example    int solution NSMutableArray  array         NSArray  sortedArray    array sortedArrayUsingSelector   selector compare          int x   1       for  NSNumber  number in sortedArray            if  number intValue  lt  0             continue                  if  x  lt  number intValue            return x                 x   number intValue   1               return x

User · Answer

public static int solution int   A        Arrays sort A       int minNumber   1      int length   A length - 1      int max   A length       Set  lt  Integer  gt  set   new HashSet  lt   gt          for  int i  A            if  i  gt  0                set add i                       for  int j   1  j  lt   max   1  j              if   set contains j                 minNumber   j              break                      return minNumber

User · Answer

x000D   x000D     Codility Interview Question Solved Using Javascript  const newArray         used in comparison to array with which the solution is required  const solution    number    gt        function with array parameter  number    const largest   number reduce  num1  num2    gt        return num1  gt  num2         num1         num2    finds the largest number in the array to                                    be used as benchmark for the new array to                                    be created            const range   1   largest    for       let x   1      x  lt   range      x     loop to populate new array with positive integers           if  x  gt  range          break            newArray push x         console log  This is the number array       number           array passed   console log  This is the new array       newArray           array formed in relation to array passed   const newerArray   newArray filter  elements    gt          array formed frome unique values of  newArray      return number indexOf elements     -1          console log       These are numbers not present in the number array      newerArray         const lowestInteger   newerArray reduce  first  second    gt          newerArray reduced to its lowest possible element by finding the least element in the array     return first  lt  second   first   second          console log  The lowest positive integer is     lowestInteger      solution  1  2  3  4  6      solution function to find the lowest possible integer invoked x000D   x000D   x000D

User · Answer

Java Solution -  Inside de method solution   int N   A length   Set lt Integer gt  set   new HashSet lt  gt     for  int a   A        if  a  gt  0            set add a            if set size    0        return N 1     for  int i   1  i  lt   N   1  i          if   set contains i             N  i          break          return N

User · Answer

My answer in Ruby  def smallest pos integer arr    sorted array   arr select   x  x  gt   1  sort   res   1    for i in  0  sorted array length - 1      if res  lt  sorted array i        return res     end     res   sorted array i    1   end   res end

User · Answer

JavaScript solution without sort  100  score and O N  runtime  It builds a hash set of the positive numbers while finding the max number  function solution A        set   new Set       let max   0     for  let i 0  i lt A length  i              if  A i   gt  0                set add A i               max   Math max max  A i                        for  let i 1  i lt max  i              if   set has i                 return i                     return max 1

User · Answer

Not the best C   but it got 100  score https   app codility com demo results demoCNNMBE-B5W      you can use includes  for example   include  lt algorithm gt   include  lt iostream gt      you can write to stdout for debugging purposes  e g     cout  lt  lt   this is a debug message   lt  lt  endl   template  lt class T gt  bool allneg const T start  const T end        T it      for  it   start  it    end  it              if   it  gt   0  return false             return true     int solution vector lt int gt   amp A        if A empty    throw std  invalid argument  unexpected empty vector         std  sort A begin   A end                for size t i   0  i  lt  A size    i              std  cout  lt  lt  A i   lt  lt                    if allneg A begin   A end              return 1            int v   1      auto it   A begin        while it  A end             if std  binary search it A end   v                v              else               return v                    it              return v      Based on Fastest way to find smallest missing integer from list of integers and slightly faster than the above https   app codility com demo results demoCJ7MDF-CDD   int solution vector lt int gt   amp A           write your code in C  14  g   6 2 0      std  vector lt bool gt  negative 1000000 false       std  vector lt bool gt  non negative 1000000 1 false       bool contain negative   false      bool contain non negative   false      for int a   A           if a lt 0                negative -a    true              contain negative   true            else               non negative a    true              contain non negative   true                      int result   1      if contain negative  amp  amp   contain non negative           return result        else           for size t i   1  i  lt  non negative size    i                 if  non negative i                    result   i                  break                                    return result

User · Answer

First let me explain about the algorithm down below  If the array contains no elements then return 1  Then in a loop check if the current element of the array is larger then the previous element by 2 then there is the first smallest missing integer  return it  If the current element is consecutive to the previous element then the current smallest missing integer is the current integer   1      Array sort A        if A Length    0  return 1       int last    A 0   lt  1    0   A 0        for  int i   0  i  lt  A Length  i                  if A i   gt  0               if  A i  - last  gt  1  return last   1              else last   A i                         return last   1

User · Answer

def solution A   A   sorted filter lambda x  x  gt   0  A   if A is         return 1 for i in range 1  100000       if i not in A          return i

User · Answer

This is my solution written in ruby simple  correct and efficient   def solution arr     sorted   arr uniq sort   last   sorted last   return 1 unless last  gt  0    i   1   sorted each do  num      next unless num  gt  0     return i unless num    i      i    1   end   i  end

User · Answer

The code below is is simpler but my motive was to write for JavaScript  ES6 users   function solution A         let s   A sort        let max   s s length-1       let r   1       for let i 1  i  lt    max   1   i              r    A includes i    1   i           if r gt 1  break             return r

User · Answer

I find another solution to do it with additional storage         if A    -1 2  the solution works fine      public static int solution int   A         int N   A length       int   C   new int N                  Mark A i  as visited by making A A i  - 1  negative               for  int i   0  i  lt  N  i                             we need the absolute value for the duplicates                       int j   Math abs A i   - 1           if  j  gt   0  amp  amp  j  lt  N  amp  amp  A j   gt  0                C j    -A j                        for  int i   0  i  lt  N  i               if  C i     0                return i   1                       return N   1

User · Answer

This my implementation in Swift 4 with 100  Score  It should be a pretty similar code in Java  Let me know what you think  public func solution   A   inout  Int   - gt  Int     let B   A filter   element in     element  gt  0      sorted      var result   1   for element in B       if element    result         result   result   1       else if element  gt  result         break              return result

User · Answer

in C  static int solutionA int   A                Array Sort A            int minNumber   1           if A Max    lt  0                        return minNumber                     for  int i   0  i  lt  A Length  i                          if  A i     minNumber                                minNumber                                           if  A i   gt  minNumber                                break                                   return minNumber         100  Test Pass https   i stack imgur com FvPR8 png

User · Answer

My solution     public int solution int   A            int N   A length          Set lt Integer gt  set   new HashSet lt  gt             for  int a   A                if  a  gt  0                    set add a                                   for  int index   1  index  lt   N  index                  if   set contains index                     return index                                  return N   1

User · Answer

I was thinking about another approach  JS  JavaScript  and got this results that score 66  because of performance issues      const properSet   A filter  item    gt    return item  gt  0         let biggestOutsideOfArray   Math max    properSet            if  biggestOutsideOfArray     -Infinity           biggestOutsideOfArray   1        else           biggestOutsideOfArray    1                for  let i   1  i  lt   biggestOutsideOfArray  i             if properSet includes i      false               return i

User · Answer

This solution is in Javascript but complete the test with 100  score and less codes  function solution A        let s   A sort  a  b    gt    return a - b        let x   s find o   gt   s includes o 1   amp  amp  o gt 0      return   x lt 0      s includes 1     1   x 1

User · Answer

This is might help you  it should work fine   public static int sol int   A        boolean flag  false      for int i 1  i lt  1000000 i               for int j 0 j lt A length j                  if A j   i                    flag   false                  break               else                   flag   true                                  if flag                return i                      return 1

User · Answer

I tried it with Swift and got 100    public func solution   A   inout  Int   - gt  Int      write your code in Swift 4 2 1  Linux  if A count    0       return 1   A   A sorted   if A A count - 1   lt   0       return 1    var temp   1  for numb in A        if numb  gt  0            if numb    temp               temp    1          else if numb     temp - 1                return temp                    return temp

User · Answer

You re doing too much  You ve create a TreeSet which is an order set of integers  then you ve tried to turn that back into an array  Instead go through the list  and skip all negative values  then once you find positive values start counting the index  If the index is greater than the number  then the set has skipped a positive value   int index   1  for int a  set       if a gt 0           if a gt index               return index            else              index                      return index    Updated for negative values   A different solution that is O n  would be to use an array  This is like the hash solution   int N   A length  int   hashed   new int N    for  int i  A       if i gt 0  amp  amp  i lt  N           hashed i-1    1           for int i   0  i lt N  i         if hash i   0           return i 1          return N 1    This could be further optimized counting down the upper limit for the second loop

User · Answer

Swift version using functions rather than an iterative approach  The solution obtained perfect score  - Codility  This solution uses functions rather than an iterative approach  So the solution relies heavily on the language s optimizations  A similar approach could be done in Java such as using Java s set operations and other functions  public func solution   A   inout  Int   - gt  Int       let positives   A filter   0  gt  0      let max   positives count  lt   100 000   positives count   1   100 001     return Set 1   max  subtracting A  min      -1     Obtained all positive numbers from the source array  Obtained all possible results based on the positive count  Limited the set to 100k as stated in the problem  Added 1 in case the source array was a complete sequence  Returned the minimum positive number after excluding the source array s elements from the set of all possible results   Note  The function declaration was from Codility and inout was unneeded  Returning an integer did not allow for nil so -1 was used

User · Answer

For JavaScript i would do it this way   function solution arr        let minValue   1       arr sort         if  arr arr length - 1   gt  0                for  let i   0  i  lt  arr length  i                          if  arr i      minValue                                minValue   minValue   1                            if  arr i   gt  minValue                                break                                     return minValue      Tested it with the following sample data   console log solution  1  3  6  4  1  2     console log solution  1  2  3     console log solution  -1  -3

User · Answer

For the space complexity of O 1  and time complexity of O N  and if the array can be modified then it could be as follows  public int getFirstSmallestPositiveNumber int   arr           set positions of non-positive or out of range elements as free  use 0 as marker      for  int i   0  i  lt  arr length  i              if  arr i   lt   0    arr i   gt  arr length                arr i    0                         iterate through the whole array again mapping elements  1 n  to positions  0  n-1      for  int i   0  i  lt  arr length  i              int prev   arr i              while elements are not on their correct positions keep putting them there         while  prev  gt  0  amp  amp  arr prev - 1     prev                int next   arr prev - 1               arr prev - 1    prev              prev   next                          now  the first unmapped position is the smallest element     for  int i   0  i  lt  arr length  i              if  arr i     i   1                return i   1                      return arr length   1      Test public void testGetFirstSmallestPositiveNumber         int     arrays   new int      1 -1 -5 -3 3 4 2 8          5  4  3  2  1           0  3  -2  -1  1         for  int i   0  i  lt  arrays length  i              System out println getFirstSmallestPositiveNumber arrays i                Output   5 6 2

User · Answer

This code has been writen in Java SE 8  import java util     public class Solution       public int solution int   A                     int smallestPositiveInt   1            if A length    0                return smallestPositiveInt                     Arrays sort A            if A 0   gt  1                return smallestPositiveInt                     if A A length - 1   lt   0                 return smallestPositiveInt                     for int x   0  x  lt  A length  x                  if A x     smallestPositiveInt                     smallestPositiveInt                                          return smallestPositiveInt

User · Answer

Here s my JavaScript solution which scored 100  with O N  or O N   log N   detected time complexity   function solution A        let tmpArr   new Array 1        for  const currNum of A            if  currNum  gt  arr length                tmpArr length   currNum                    tmpArr currNum - 1    true             return  tmpArr findIndex  element    gt  element     undefined    1      tmpArr length   1

User · Answer

My code in Java  100  result in Codility  import java util     class Solution      public int solution int   arr         int smallestInt   1        if arr length    0  return smallestInt       Arrays sort arr        if arr 0   gt  1  return smallestInt      if arr  arr length - 1   lt   0   return smallestInt        for int i   0  i  lt  arr length  i             if arr i     smallestInt             smallestInt                    return smallestInt

User · Answer

This is my solution  First we start with 1  we loop over the array and compare with 2 elements from the array  if it matches one of the element we increment by 1 and start the process all over again   private static int findSmallest int max  int   A         if  A    null    A length    0          return max       for  int i   0  i  lt  A length  i              if  i    A length - 1                if  max    A i                   return max              else                 return max   1            else if   checkIfUnique max  A i   A i   1                return findSmallest max   1  A             return max      private static boolean checkIfUnique int number  int n1  int n2        return number    n1  amp  amp  number    n2

User · Answer

JS  x000D   x000D  function solution A         let x   1          A filter x   gt  x  gt   1        sort  a  b    gt  a - b        map  val  i  arr    gt            if x  lt  arr i   return         x   arr i    1             return x    console log solution  3  4  -1  1     console log solution  1  2  0     x000D   x000D   x000D

User · Answer

The simplest way using while loop    fun solution A  IntArray   Int       var value   1     var find   false     while value  lt  A size            val iterator   A iterator           while  iterator hasNext                  if  value    iterator nextInt                      find   true                 value                                   if   find                break           else               find   false                     return value

User · Answer

My Java solution got 100   I feel this is simple and the complexity is O n    public int solution int   A        Integer s   1      List lt Integer gt  list   new ArrayList lt  gt          for  int i   A            if  i gt 0                list add i                        Collections sort list        for  int i   list            if  s  lt  i                return s                    s   i   1             return s      Let me know if we can improve this more

User · Answer

Try this code it works for me      import java util        class Solution           public static int solution int   A                   write your code in Java SE 8             int m   Arrays stream A  max   getAsInt      Storing maximum value              if  m  lt  1     In case all values in our array are negative                                 return 1                              if  A length    1                        If it contains only one element                  if  A 0     1                         return 2                     else                        return 1                                                 int min   A 0               int max  A 0               int sm   1               HashSet lt Integer gt  set   new HashSet lt Integer gt                  for int i 0 i lt A length i                     set add A i                     if A i  lt min                       min   A i                                     if A i  gt max                       max   A i                                                if min  lt   0                   min   1                             if max  lt   0                   max   1                             boolean fnd   false              for int i min i lt  max i                     if i gt 0  amp  amp   set contains i                        sm   i                      fnd   true                      break                                    else continue                             if fnd                  return sm               else return max  1                           public static void main String args                     Scanner s new Scanner System in                System out println  enter number of elements                 int n s nextInt                 int arr   new int n                System out println  enter elements                 for int i 0 i lt n i      for reading array                 arr i  s nextInt                            int array     arr              Calling getMax   method for getting max value         int max   solution array           System out println  Maximum Value is    max

User · Answer

For Swift 4  func solution   A    Int   - gt  Int        var positive   A filter    0  gt  0   sorted        var x   1      for val in positive         if we find a smaller number no need to continue  cause the array is sorted     if x  lt  val            return x           x   val   1   return x

User · Answer

Late joining the conversation  Based on   https   codereview stackexchange com a 179091 184415   There is indeed an O n  complexity solution to this problem even if duplicate ints are involved in the input   solution A  Filter out non-positive values from A For each int in filtered     Let a zero-based index be the absolute value of the int - 1     If the filtered range can be accessed by that index  and  filtered index  is not negative         Make the value in filtered index  negative  For each index in filtered     if filtered index  is positive         return the index   1  to one-based   If none of the elements in filtered is positive     return the length of filtered   1  to one-based   So an array A    1  2  3  5  6   would have the following transformations   abs A 0     1  to 0idx   0  A 0    1  make negative A 0    A    -1   2   3   5   6  abs A 1     2  to 0idx   1  A 1    2  make negative A 1    A    -1  -2   3   5   6  abs A 2     3  to 0idx   2  A 2    3  make negative A 2    A    -1  -2  -3   5   6  abs A 3     5  to 0idx   4  A 4    6  make negative A 4    A    -1  -2  -3   5  -6  abs A 4     6  to 0idx   5  A 5  is inaccessible           A    -1  -2  -3   5  -6   A linear search for the first positive value returns an index of 3  Converting back to a one-based index results in solution A  3 1 4   Here s an implementation of the suggested algorithm in C   should be trivial to convert it over to Java lingo - cut me some slack common    public int solution int   A        var positivesOnlySet   A          Where x   gt  x  gt  0           ToArray         if   positivesOnlySet Any            return 1       var totalCount   positivesOnlySet Length      for  var i   0  i  lt  totalCount  i      O n  complexity               var abs   Math Abs positivesOnlySet i   - 1          if  abs  lt  totalCount  amp  amp  positivesOnlySet abs   gt  0    notice the greater than zero check              positivesOnlySet abs    -positivesOnlySet abs              for  var i   0  i  lt  totalCount  i      O n  complexity               if  positivesOnlySet i   gt  0              return i   1             return totalCount   1

User · Answer

In PHP I can achieve it from a few lines of code  function solution  A      for  i 1  in array  i  A    i       return  i

User · Answer

Swift with  reduce    public func solution   A   inout  Int   - gt  Int       return A filter    0  gt  0   sorted   reduce 1     0  lt   1    0    1   1

User · Answer

The below C   solution obtained a 100  score  The theoretical complexity of the code is  Time Complexity   O N  amortized due to hash set and Auxiliary Space complexity of O N  due to use of hash for lookup in O 1  time   include lt iostream gt   include lt string gt   include lt vector gt   include lt climits gt   include lt cmath gt   include lt unordered set gt   using namespace std   int solution vector lt int gt  amp  A      if  A size        return 1      unordered set lt int gt  hashSet    int maxItem INT MIN    for const auto amp  item   A          hashSet insert item       if maxItem lt item        maxItem item         if maxItem lt 1      return 1      for int i 1 i lt  maxItem   i          if hashSet find i   hashSet end          return i         return maxItem 1

User · Answer

You could simply use this  which is a variant of Insertion-Sort  without the need of Set  or sorting the whole array      public static int solution int   A          we can choose only positive integers to enhance performance         A   Arrays stream A  filter i - gt  i  gt  0  toArray            for int i 1  i lt A length  i                 int v1   A i               int j   i-1              while  j  gt  -1  amp  amp  A j   gt  v1                    A j   1    A j                   j   j - 1                            A j   1    v1              if A i  - A i-1   gt  1                   return A i    1                                  return 1

User · Answer

No need to store anything  No need for hashsets   Extra memory   You can do it as you move through the array  However  The array has to be sorted  And we know the very most minimum value is 1 import java util Arrays  class Solution       public int solution int   A            Arrays sort A                int min   1           int cap   A length    for efficiency     no need to calculate or access the array object   s length property per iteration                   for  int i   0  i  lt  cap  i                 if A i     min                   min                   can add else if A i   gt  min  break  as suggested by punit                        min     min  lt   0     1 min    this means  if  min  lt   0   min  1 else min   min  you can also do  if min  lt 1 for better efficiency less jumps         return min

User · Answer

I ve not seen a C  solution that uses Linq yet    the following is the simplest way  I think  to get 100  pass on this test   using System  using System Linq   class Solution       public int solution int   A    gt  Enumerable Range 1  100001  Except A  Min        However  I should note that whilst the above is simple  and will get 100  pass on the test  it s not the most efficient  For a more efficient Linq solution  something like the following will work better   using System  using System Collections Generic   public static int solution int   A        var set   new HashSet lt int gt  A        return Enumerable Range 1  A Length   1  First i   gt   set Contains i

User · Answer

The code below will run in O N  time and O N  space complexity  Check this codility link for complete running report   The program first put all the values inside a HashMap meanwhile finding the max number in the array  The reason for doing this is to have only unique values in provided array and later check them in constant time  After this  another loop will run until the max found number and will return the first integer that is not present in the array      static int solution int   A          int max   -1        HashMap lt Integer  Boolean gt  dict   new HashMap lt  gt           for int a   A             if dict get a     null                dict put a  Boolean TRUE                       if max lt a                max   a                           for int i   1  i lt max  i               if dict get i     null                return i                           return max gt 0   max 1   1

User · Answer

My solution in JavaScript  using the reduce   method  function solution A         the smallest positive integer   1   if   A includes 1   return 1        greater than 1   return A reduce  accumulator  current    gt        if  current  lt   0  return accumulator     const min   current   1     return  A includes min   amp  amp  accumulator  gt  min   min   accumulator       1000000     console log solution  1  2  3       4 console log solution  5  3  2  1  -1       4 console log solution  -1  -3       1 console log solution  2  3  4       1   https   codesandbox io s the-smallest-positive-integer-zu4s2

User · Answer

100  result solution in Javascript   function solution A           only positive values  sorted     A   A filter x   gt  x  gt   1  sort  a  b    gt  a - b       let x   1      for let i   0  i  lt  A length  i                 if we find a smaller number no need to continue  cause the array is sorted         if x  lt  A i                 return x                   x   A i    1            return x

User · Answer

Here is my PHP solution  100  Task Score  100  correctness  and 100  performance  First we iterate and we store all positive elements  then we check if they exist   function solution  A          B           foreach  A as  a            if  a  gt  0   B      a                 i   1       last   0      sort  B        foreach  B as  b            if  last     b   i--     Check for repeated elements         else if  i     b  return  i            i             last    b                      return  i      I think its one of the clears and simples functions here  the logic can be applied in all the other languages

User · Answer

Solution in JavaScript   function solution A        let smallestInt   1       function existsInArray val            return A find  a    gt  a     val              for  let index   smallestInt  index  lt  1000000  index              if  existsInArray index   amp  amp   existsInArray index   1   amp  amp              existsInArray smallestInt                 smallestInt   index   1                     return smallestInt

User · Answer

I think that using structures such as  sets or dicts to store unique values is not the better solution  because you end either looking for an element inside a loop which leads to O N N  complexity or using another loop to verify the missing value which leaves you with O N  linear complexity but spending more time than just 1 loop   Neither using a counter array structure is optimal regarding storage space because you end up allocating MaxValue blocks of memory even when your array only has one item   So I think the best solution uses just one for-loop  avoiding structures and also implementing conditions to stop iteration when it is not needed anymore   public int solution int   A           write your code in Java SE 8     int len   A length      int min 1       Arrays sort A        if A len-1  gt 0      for int i 0  i lt len  i             if A i  gt 0               if A i   min  min min 1              if A i  gt min  break                      return min      This way you will get complexity of O N  or O N   log N    so in the better case you are under O N  complexity

User · Answer

Here is the code in python with comments to understand the code - Codility 100  Missing Integer  Code-  def solution A       solution at https   app codility com demo results trainingV4KX2W-3KS  100  idea is to take temp array of max length of array items for all positive use item of array as index and mark in tem array as 1 ie  present item traverse again temp array if first found value in tem array is zero that index is the smallest positive integer  param A   return      max value   max A  if max value  lt  1        max is less than 1 ie  1 is the smallest positive integer     return 1 if len A     1        one element with 1 value     if A 0     1          return 2       one element other than 1 value     return 1   take array of length max value   this will work as set ie  using original array value as index for this array temp max len array    0    max value for i in range len A          do only for positive items     if A i   gt  0            check at index for the value in A         if temp max len array A i  - 1     1                set that as 1             temp max len array A i  - 1    1 print temp max len array  for i in range len temp max len array          first zero ie  this index is the smallest positive integer     if temp max len array i     0          return i   1   if no value found between 1 to max then last value should be smallest one return i   2    arr    2  3  6  4  1  2       result   solution arr

User · Answer

In C   bur need improvement       public int solution int   A              int retorno   0            for  int i   0  i  lt  A Length  i                                  int ultimovalor   A i    1                  if   A Contains ultimovalor                                         retorno    ultimovalor                       if  retorno  lt   0  retorno   1                                              return retorno

User · Answer

This answer gives 100  in Python  Worst case complexity O N    The idea is that we do not care about negative numbers in the sequence  since we want to find the smallest positive integer not in the sequence A   Hence we can set all negative numbers to zero and keep only the unique positive values  Then we check iteratively starting from 1 whether the number is in the set of positive values of sequence A   Worst case scenario  where the sequence is an arithmetic progression with constant difference 1   leads to iterating through all elements  and thus O N  complexity   In the extreme case where all the elements of the sequence are negative  i e  the maximum is negative  we can immediately return 1 as the minimum positive number   def solution A       max A max A      B set  a if a gt  0 else 0 for a in A        b 1     if max A lt  0          return 1      else          while b in B              b  1         return b

User · Answer

100  result solution in Javascript   function solution A     let N i 1      A       new Set A       remove duplicated numbers form the Array     A   A filter x   gt  x  gt   1  sort  a  b    gt  a - b       remove negative numbers  amp  sort array     while  N      do not stop untel N get a value       if A i-1     i  N i         i              return N

User · Answer

100  solution in Swift  I found it here  it is really beautiful than mine algo    No need to turn array as ordered  instead using dictionary  Int  Bool  and just check the positive item in dictionary   public func solution   A   inout  Int   - gt  Int       var counter    Int  Bool        for i in A           counter i    true            var i   1     while true           if counter i     nil               return i           else               i    1

User · Answer

This works very well for java  It uses bitwise exclusive OR and assignment operator      public int solution int   A               write your code in Java SE 8         int sol   0          for int val A               sol    val                    return sol

User · Answer

This solution is in c  but complete the test with 100  score  public int solution int   A           write your code in C  6 0 with  NET 4 5  Mono      var positives   A Where x   gt  x  gt  0  Distinct   OrderBy x   gt  x  ToArray        if positives Count      0  return 1      int prev   0      for int i  0  i  lt  positives Count    i              if positives i     prev   1               return prev   1                     prev   positives i             return positives Last     1

User · Answer

My recursive solution   class Solution       public int solution int   A            return next 1  A             public int next int b  int   A            for  int a   A               if  b  a                  return next   b  A                     return b

User · Answer

Rewrite the accepted answer with Swift  Hashset in Swift is Set  I think if index is required as return value then try to use Dictionary instead  Passed with 100  score  public func solution   A   Int   - gt  Int       let n   A count     var aSet   Set lt Int gt             for a in A           if a  gt  0               aSet insert a                           for i in 1   n 1           if  aSet contains i                return i                          return 1

User · Answer

Simple way to get this done     public int  findNearestPositive int array          boolean isNegative false      int number 0      int value 0       if array 0  lt  0  amp  amp  array array length-1  lt 0            return 1               for int i 0 i lt array length i              value i 1      isNegative false       for int j 0 j lt array length j              if value  array j             isNegative true                     if isNegative  true            if number  0        number value       else if value lt number       number value                                           if number  0             number value 1             return number

User · Answer

Python implementation of the solution  Get the set of the array - This ensures we have unique elements only  Then keep checking until the value is not present in the set - Print the next value as output and return it     def solution A     write your code in Python 3 6     a   set A      i   1     while True          if i in A              i  1         else              return i     return i     pass

User · Answer

public int solution int   A         int res   0      HashSet lt Integer gt  list   new HashSet lt  gt          for  int i   A  list add i       for  int i   1  i  lt  1000000  i              if  list contains i                res   i              break                      return res

User · Answer

My simple and  time  efficient Java solution   import java util     class Solution       public int solution int   A            Set lt Integer gt  set new TreeSet lt  gt             for  int x A                if  x gt 0                    set add x                                    int y 1          Iterator lt Integer gt  it set iterator            while  it hasNext                  int curr it next                if  curr  y                    return y                            y                      return y

User · Answer

This is the solution in C   using System     you can also use other imports  for example  using System Collections Generic      you can write to stdout for debugging purposes  e g     Console WriteLine  quot this is a debug message quot     class Solution   public int solution int   A           write your code in C  6 0 with  NET 4 5  Mono  int N   A Length  HashSet lt int gt  set  new HashSet lt int gt     foreach  int a in A    if  a  gt  0        set Add a           for  int i   1  i  lt   N   1  i      if   set Contains i         return i          return N

User · Answer

The shortest PHP solution  function solution  A           write your code in PHP7 0      lastNum   1       while in array  lastNum   A              lastNum               return  lastNum

User · Answer

Below is my solution int   A    1 2 3   Arrays sort A   Set lt Integer gt  positiveSet   new HashSet lt  gt     for int a  A        if a gt 0            positiveSet add a           for int a  A        int res   a 1      if  positiveSet contains res             System out println  quot result    quot  res           break

User · Answer

Here is an efficient python solution   def solution A       m   max A      if m  lt  1         return 1      A   set A      B   set range 1  m   1       D   B - A     if len D     0          return m   1     else          return min D

User · Answer

How about just playing around with loops  import java util Arrays  public class SmallestPositiveNumber        public int solution int   A            Arrays sort A           int SPI   1           if A length  lt   1  return SPI           for int i 0  i lt A length-1  i                  if  A i 1  - A i    gt  1                                return A i    1                                  return A A length-1  1

User · Answer

This is my approach with Java   The time complexity of this answer is 2 O N  because I iterate through Array A twice   import java util HashMap   public static final Integer solution int   A        HashMap lt Integer  Integer gt  map   new HashMap lt  gt  A length     O n  space      for  int i   A            if   map containsKey i                 map put i  i                        int minorPositive   100000      for  int i   A            if   map containsKey i   1                 if  i  lt  minorPositive                    minorPositive   i   1                                     if  minorPositive  lt  0           minorPositive   1            return minorPositive

User · Answer

function solution A             return  A  amp  amp  A          filter num   gt  num  gt  0           sort  a  b    gt  a - b           reduce  acc  curr  idx  arr    gt                arr includes acc   1    acc   curr  0              1      solution       1 solution null      1 solution         1 solution  0  0  0       1

User · Answer

I figured an easy way to do this was to use a BitSet   just add all the positive numbers to the BitSet  when finished  return the index of the first clear bit after bit 0   public static int find int   arr        BitSet b   new BitSet        for  int i   arr            if  i  gt  0                b set i                       return b nextClearBit 1

User · Answer

lt JAVA gt  Try this code-  private int solution int   A     Our original array          int m   Arrays stream A  max   getAsInt      Storing maximum value         if  m  lt  1     In case all values in our array are negative                       return 1                    if  A length    1                   If it contains only one element             if  A 0     1                    return 2                else                   return 1                                  int i   0          int   l   new int m           for  i   0  i  lt  A length  i                  if  A i   gt  0                    if  l A i  - 1     1    Changing the value status at the index of our list                                       l A i  - 1    1                                                    for  i   0  i  lt  l length  i      Encountering first 0  i e  the element with least value                       if  l i     0                    return i   1                                    In case all values are filled between 1 and m         return i 1        Input   1 -1 0    o p  2 Input   1 2 5 4 6   o p  3 Input   -1 0 -2   o p  1

User · Answer

My python solution 100  correctness def solution A      if max A   lt  1      return 1    if len A     1 and A 0     1      return 1    s   set     for a in A      if a  gt  0        s add a          for i in range 1  len A        if i not in s        return i    return len s    1  assert solution  1  3  6  4  1  2      5 assert solution  1  2  3      4 assert solution  -1  -3      1 assert solution  -3 1 2      3 assert solution  1000      1

User · Answer

I achieved 100  on this by the below solution in Python -  def solution A      a frozenset sorted A      m max a     if m gt 0         for i in range 1 m              if i not in a                return i        else            return m 1    else         return 1

User · Answer

Solution in Scala with all test cases running    Class Solution      def smallestNumber arrayOfNumbers  Array Int           val filteredSet   arrayOfNumbers foldLeft HashSet empty Int    acc  next         gt  if next  gt  0  acc   next  else acc      getSmallestNumber filteredSet           tailrec   private def getSmallestNumber setOfNumbers  HashSet Int   index  Int   1      Int           setOfNumbers match           case emptySet if emptySet isEmpty    gt  index         case set   gt  if  set contains index   index else getSmallestNumber set             index   1

User · Answer

Works 100   tested with all the condition as described     MissingInteger     public int missingIntegerSolution int   A            Arrays sort A           long sum   0          for int i 0  i lt  A A length-1   i                  sum    i                      Set lt Integer gt  mySet   Arrays stream A  boxed   collect Collectors toSet             Integer   B   mySet toArray new Integer 0            if sum  lt  0              return 1           for int i 0  i lt B length  i                  sum -  B i                      if sum    0               return A A length-1    1          else             return Integer parseInt    sum          int   j    1  3  6  4  1  2 5    System out println  Missing Integer     obj missingIntegerSolution j      Output Missing Integer   7  int   j    1  3  6  4  1  2   System out println  Missing Integer     obj missingIntegerSolution j      Output Missing Integer   5

[java] Find the smallest positive integer that does not occur in a given sequence

Examples related to java

Examples related to algorithm