Missing integer variation - O(n) solution needed [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Guide the asker to update the question so it focuses on a single, specific problem. Narrowing the question will help others answer the question concisely. You may edit the question if you feel you can improve it yourself. If edited, the question will be reviewed and might be reopened.

Closed 7 years ago.

Improve this question

The problem comes from Codility programming training and it sounds as follows: we have an array (A[]) with n (ranging from 1 to 100,000) elements and these are our parameters. The elements of the array are integers from −2,147,483,648 to 2,147,483,647, and we need to find smallest positive integer that is NOT in the array. Of course this could be done easily in O(n*log n) by sorting them all and going through the sorted array, looking for the missing posiitve number (this last operation has O(n) worst time complexity in my solution). But according to Codility, this ENTIRE problem can be done in O(n), and I cannot see any way to do that. Could someone give some tips to let me get un-stuck?

PS Here is a link to detailed description of the problem which I'm not allowed to copy - https://codility.com/c/intro/demo35UEXH-EAT

• sds: is it okay to allocate temp storage of size O(n)?
• Miserable Variable: Questions asking for correct algorithm are not appropriate on SO, try codegolf.stackexchange.com. That said, you can iterate the array till you find the first positive integer and initialize the result to that number; and then iterate the rest modifying the result when a you find a number smaller than current result.
• Miserable Variable: This question appears to be off-topic because it is asking for "best algorithm"
• Gassa: What's up with closing as too broad? The question contains an exact and formal problem statement: how to do one specific thing in O(n). Generally, I sometimes see algorithm questions being closed when code is secondary to algorithm, but fail to understand why: it's still a programming question, the algorithm tag has 85.5k questions, and the tour suggests "Software algorithms" are on-topic as the second of the four check marks. If such questions are not welcome here, please kindly educate me why.

Answer 1

By pigeonhole principle, at least one of the numbers 1, 2, ..., n+1 is not in the array. Let us create a boolean array b of size n+1 to store whether each of these numbers is present.

Now, we process the input array. If we find a number from 1 to n+1, we mark the corresponding entry in b. If the number we see does not fit into these bounds, just discard it and proceed to the next one. Both cases are O(1) per input entry, total O(n).

After we are done processing the input, we can find the first non-marked entry in our boolean array b trivially in O(n).

• Gassa: @sammy333: This notion does not invalidate the solution: the input numbers can be any signed int32s, but we are interested only in the occurrences of 1, 2, ..., n + 1 among them, as one of these is guaranteed to be the answer.
• Cristian: 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]. Your solution only works when the max element in the array is 100,000.
• Gassa: @Cristian But the answer is always from 1 to 100,001, and that's the fact we use. Please read again.
• alayor: What about this array: [1, 299999] The value of N = 2. So, should I create a boolean array of size 3? How can I return the correct result 2 from this boolean array?
• Bruno Negrão Zica: I implemented your algorithm and it really works in O(N)!: public int solution(int[] A) { if (A.length == 0 || A.length == 1 && (A[0] > 1 || A[0] <=0) ) { return 1; } boolean [] b = new boolean [A.length + 1]; for (int element: A) { if (element < 0 || element > b.length - 1) { continue; } b[element] = true; } int i = 1; for (; i<b.length; i++) { if (b[i] == false) { return i; } } return i; }

Answer 2

Simple solution 100% in Java.

Please note it is O(nlogn) solution but gives 100% result in codility.

public static int solution(final int[] A) 
{ 
 Arrays.sort(A);
 int min = 1;
 // Starting from 1 (min), compare all elements, if it does not match 
 // that would the missing number.
 for (int i : A) {
 if (i == min) {
 min++;
 }
 }
 return min;
}

• shanahobo86: Simple and more performant than other solutions posted. Very nice!
• Eric MaCarthy: Very simple and helpful for me to understand the problem
• swanhella: This is O(n log n) not O(n) due to the sorting.
• Anand: I understand it is o(nlogn) solution, but it gives 100% result in codility.
• flow2k: This is a clever one. For a small improvement, we can add another branch after if (i == min) - if i > min, we can return min right away.

Answer 3

wrote this today and got 100/100. not the most elegant solution, but easy to understand -

public int solution(int[] A) {
 int max = A.length;
 int threshold = 1;
 boolean[] bitmap = new boolean[max + 1];
 //populate bitmap and also find highest positive int in input list.
 for (int i = 0; i < A.length; i++) {
 if (A[i] > 0 && A[i] <= max) {
 bitmap[A[i]] = true;
 }
 if (A[i] > threshold) {
 threshold = A[i];
 }
 }
 //find the first positive number in bitmap that is false.
 for (int i = 1; i < bitmap.length; i++) {
 if (!bitmap[i]) {
 return i;
 }
 }
 //this is to handle the case when input array is not missing any element.
 return (threshold+1);
}

• Quest Monger: Is someone downvoting all the solutions? comments were included in the code in my case.

Answer 4

public int solutionMissingInteger(int[] A) {
 int solution = 1;
 HashSet<Integer> hashSet = new HashSet<>();
 for(int i=0; i<A.length; ++i){
 if(A[i]<1) continue;
 if(hashSet.add(A[i])){
 //this int was not handled before
 while(hashSet.contains(solution)){
 solution++;
 }
 }
 }
 return solution;
}

• Cathal: Thanks Marian, this answer give me 100% in Swift 3 also.

Answer 5

Simple Java soution. Scored 100/100 in correctness and performance.

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

Answer 6

Build a hash table of all the values. For the numbers 1 to n + 1, check if they are in the hash table. At least one of them is not. Print out the lowest such number.

This is O(n) expected time (you can get with high probability). See @Gassa's answer for how to avoid the hash table in favor of a lookup table of size O(n).

• Gassa: No need to hash: as we know that the answer is in the first n+1 positive integers, we can consider just them and discard everything else. See my answer for details.
• Niklas B.: @Gassa Interesting, my brain failed to make that simple progression

Answer 7

JavaScript 100%

function solution(A) {
 let sortedOb = {};
 let biggest = 0;
 A.forEach(el => {
 if (el > 0) {
 sortedOb[el] = 0;
 biggest = el > biggest ? el : biggest;
 }
 });
 let arr = Object.keys(sortedOb).map(el => +el);
 if (arr.length == 0) return 1;
 for(let i = 1; i <= biggest; i++) {
 if (sortedOb[i] === undefined) return i;
 }
 return biggest + 1;
}

Answer 8

100% Javascript

function solution(A) {
 // write your code in JavaScript (Node.js 4.0.0)
 var max = 0;
 var array = [];
 for (var i = 0; i < A.length; i++) {
 if (A[i] > 0) {
 if (A[i] > max) {
 max = A[i];
 }
 array[A[i]] = 0;
 }
 }
 var min = max;
 if (max < 1) {
 return 1;
 }
 for (var j = 1; j < max; j++) {
 if (typeof array[j] === 'undefined') {
 return j
 }
 }
 if (min === max) {
 return max + 1;
 }
 }

• ugurtemiz: You can remove min related lines. max variable is not changing after assigning max to min.

Answer 9

C# scored 100%,

Explanation: use of lookup table where we store already seen values from input array, we only care about values that are greater than 0 and lower or equal than length on input array

 public static int solution(int[] A)
 {
 var lookUpArray = new bool[A.Length];
 for (int i = 0; i < A.Length; i++)
 if (A[i] > 0 && A[i] <= A.Length)
 lookUpArray[A[i] - 1] = true;
 for (int i = 0; i < lookUpArray.Length; i++)
 if (!lookUpArray[i])
 return i + 1;
 return A.Length + 1;
 }

• alayor: Will it work with this array? [1, 233444]

Answer 10

This is my solution is Swift 4

public func solution(_ A: inout [Int]) -> Int {
 var minNum = 1
 var hashSet = Set<Int>()
 for int in A {
 if int > 0 {
 hashSet.insert(int)
 }
 }
 while hashSet.contains(minNum) {
 minNum += 1
 }
 return minNum
}
var array = [1,3,6]
solution(&array)

// Answer: 2

• mjuarez: Can you provide some more information of why this answers the OP's original question?

Answer 11

100%: the Python sort routine is not regarded as cheating...

def solution(A):
 """
 Sort the array then loop till the value is higher than expected
 """
 missing = 1
 for elem in sorted(A):
 if elem == missing:
 missing += 1
 if elem > missing:
 break
 return missing

• greybeard: Not as cheating in itself. Please argue how this is O(n).
• John Mee: Isn't it actually O(n+n)? The first one to do the sort, then a second time passing over the result of the sort. My comment is just observing that Codility don't penalize for using the sort routine with this problem.
• greybeard: Is sort O(n)? Not for comparison based sorts: Ω(nlogn).
• John Mee: Digest here and possibly here if you really want to know exactly how python2's sort is implemented.
• greybeard: Thanks, but not the point: please argue how using pythons sort is O(n).

Answer 12

It worked for me. It is not O(n), but little simpler:

import java.util.stream.*;
class Solution {
 public int solution(int[] A) {
 A = IntStream.of(A)
 .filter(x->x>0)
 .distinct()
 .sorted()
 .toArray();
 int min = 1;
 for(int val : A)
 {
 if(val==min)
 min++;
 else
 return min;
 }
 return min;
 }
}

• Samuel Pinto: This is not "expected worst-case time complexity is O(N)"

Answer 13

Swift 3 - 100%

public func solution(_ A : inout [Int]) -> Int {
// write your code in Swift 3.0 (Linux)
var solution = 1
var hashSet = Set<Int>()
 for int in A
 {
 if int > 0
 {
 hashSet.insert(int)
 while hashSet.contains(solution)
 {
 solution += 1
 }
 }
 }
 return solution
}

Thanks to Marian's answer above.

• J. Goce: How do you guys can come up with this beautiful answers?

Answer 14

My solution. 100%. In Java.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
 public int solution(int[] A) {
 Arrays.sort(A);
 ArrayList<Integer> positive = new ArrayList<>();
 for (int i = 0; i < A.length; i++) {
 if(A[i] > 0)
 positive.add(A[i]);
 }
 if(positive.isEmpty()) return 1;
 if(positive.get(0) > 1) return 1;
 for(int i = 0; i < positive.size() - 1; i++) {
 if(positive.get(i + 1) - positive.get(i) > 1)
 return positive.get(i) + 1;
 }
 return positive.get(positive.size() - 1) + 1;
 }
 public static void main(String[] args) {
 Solution solution = new Solution();
 int[] A = {-5,1,2,3,4,6,7,8,9,5};
 System.out.println(solution.solution(A)); 
 }
}

• Bruno Negrão Zica: I submitted your solution to coditily and they evaluated it as 100% correct, congratulations!

Answer 15

javascript 100% 100% first sort the array, you just need to scan positive elements so find index of 1 (if there is no 1 in array then answer is 1). then search elements after 1 till find missing number.

function solution(A) {
// write your code in JavaScript (Node.js 6.4.0)
 var missing = 1;
 // sort the array.
 A.sort(function(a, b) { return a-b });
 // try to find the 1 in sorted array if there is no 1 so answer is 1
 if ( A.indexOf(1) == -1) { return 1; }
 // just search positive numbers to find missing number 
 for ( var i = A.indexOf(1); i < A.length; i++) {
 if ( A[i] != missing) {
 missing++;
 if ( A[i] != missing ) { return missing; }
 }
 }
 // if cant find any missing number return next integer number
 return missing + 1;
}

• Rafaf Tahsin: Please format your code meta.stackexchange.com/questions/88541/…
• Viraj Parab: This code will fail for test case where 1 is not present in the array eg: [-1, -2, -5, 4,6,3]

Answer 16

I believe the solution is more involved than 'marking' corresponding values using a boolean array of n (100,000) elements. The boolean array of size n will not 'directly' map to the possible range of values (−2,147,483,648 to 2,147,483,647). This Java example I wrote attempts to map the 100K rows by mapping the value based on their offset from the max value. It also performs a modulus to reduce the resulting array to the same size as the sample element length.

/** 
 * 
 * This algorithm calculates the values from the min value and mods this offset with the size of the 100K sample size. 
 * This routine performs 3 scans. 
 * 1. Find the min/max
 * 2. Record the offsets for the positive integers
 * 3. Scan the offsets to find missing value.
 * 
 * @author Paul Goddard
 *
 */
public class SmallestPositiveIntMissing {
 static int ARRAY_SIZE = 100000;
 public static int solve(int[] array) {
 int answer = -1;
 Maxmin maxmin = getMaxmin(array);
 int range = maxmin.max - maxmin.min;
 System.out.println("min: " + maxmin.min);
 System.out.println("max: " + maxmin.max);
 System.out.println("range: " + range);
 Integer[] values = new Integer[ARRAY_SIZE];
 if (range == ARRAY_SIZE) {
 System.out.println("No gaps");
 return maxmin.max + 1;
 }
 for (int val: array) {
 if (val > 0) {
 int offset = val - maxmin.min;
 int index = offset % ARRAY_SIZE;
 values[index] = val;
 } 
 }
 for (int i = 0; i < ARRAY_SIZE; i++) {
 if (values[i] == null) {
 int missing = maxmin.min + i;
 System.out.println("Missing: " + missing);
 answer = missing;
 break;
 }
 }
 return answer;
 }
 public static Maxmin getMaxmin(int[] array) {
 int max = Integer.MIN_VALUE;
 int min = Integer.MAX_VALUE;
 for (int val:array) {
 if (val >=0) {
 if (val > max) max = val;
 if (val < min) min = val;
 }
 }
 return new Maxmin(max,min);
 }
 public static void main(String[] args) {
 int[] A = arrayBuilder();
 System.out.println("Min not in array: " + solve(A));
 }
 public static int[] arrayBuilder() {
 int[] array = new int[ARRAY_SIZE];
 Random random = new Random();
 System.out.println("array: ");
 for (int i=0;i < ARRAY_SIZE; i++) {
 array[i] = random.nextInt();
 System.out.print(array[i] + ", ");
 }
 System.out.println(" array done.");
 return array;
 }
}
class Maxmin {
 int max;
 int min;
 Maxmin(int max, int min) {
 this.max = max;
 this.min = min;
 }
}

Answer 17

Sweet Swift version. 100% correct

public func solution(inout A : [Int]) -> Int {
 //Create a Hash table
 var H = [Int:Bool]()
 // Create the minimum possible return value
 var high = 1
 //Iterate
 for i in 0..<A.count {
 // Get the highest element
 high = A[i] > high ? A[i] : high
 // Fill hash table
 if (A[i] > 0){
 H[A[i]] = true
 }
 }
 // iterate through possible values on the hash table
 for j in 1...high {
 // If you could not find it on the hash, return it
 if H[j] != true {
 return j
 } else {
 // If you went through all values on the hash
 // and can't find it, return the next higher value
 // e.g.: [1,2,3,4] returns 5
 if (j == high) {
 return high + 1
 }
 }
 }
 return high
}

Answer 18

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

Answer 19

This is my solution using python:

def solution(A):
 m = max(A)
 if m <= 0:
 return 1
 if m == 1:
 return 2
 # Build a sorted list with all elements in A
 s = sorted(list(set(A)))
 b = 0
 # Iterate over the unique list trying to find integers not existing in A
 for i in xrange(len(s)):
 x = s[i]
 # If the current element is lte 0, just skip it
 if x <= 0:
 continue;
 b = b + 1
 # If the current element is not equal to the current position,
 # it means that the current position is missing from A
 if x != b:
 return b
 return m + 1

Scored 100%/100% https://codility.com/demo/results/demoDCU7CA-SBR/

• Kostas Mouratidis: Ah, the beauty of Python is lost. A simple two-liner also gives 100%; discard negatives and make a set (no need to -explicitly- sort) A = set([a if a>0 else 0 for a in A]), then just get the set difference with the 1...N array diff = set(range(1, len(A)+2)).difference(A), and return min(diff).
• Davi Lima: How about: solution = lambda arr=[]: next(iter([i for i in range(1, len(arr) + 2) if i not in set(arr)])) or 1

Answer 20

1. Create a binary array bin of N+1 length (C uses 0 based indexing)

2. Traverse the binary array O(n)

3. If A[i] is within the bounds of bin then mark bin entry at index A[i] as present or true.
4. Traverse the binary array again
5. Index of any bin entry that is not present or false is your missing integer

~

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
int solution(int A[], int N) {
 // write your code in C99 (gcc 6.2.0)
 int i;
 bool *bin = (bool *)calloc((N+1),sizeof(bool));
 for (i = 0; i < N; i++)
 {
 if (A[i] > 0 && A[i] < N+1)
 {
 bin[A[i]] = true;
 }
 }
 for (i = 1; i < N+1; i++)
 {
 if (bin[i] == false)
 {
 break;
 }
 }
 return i;
}

• Lino: Even when your post, answers OP's question. Please provide not only a snippet that works. But explain what's happening, why it does what it should to etc.
• davegallant: this solution is O(n^2)
• Naveed Rasheed: Please explain how? This is actually O(n).
• acegs: i just tried this on codility. it got 100% though it has no free().

Answer 21

May be helpful, I am using arithmetic progression to calculate the sum, and using binary searach the element is fetched. checked with array of couple of hundred values works good. As there is one for loop and itression in step of 2, O(n/2) or less

def Missingelement (A):
 B = [x for x in range(1,max(A)+1,1)]
 n1 = len(B) - 1
 begin = 0
 end = (n1)//2
 result = 0
 print(A)
 print(B)
 if (len(A) < len(B)):
 for i in range(2,n1,2):
 if BinSum(A,begin,end) > BinSum(B,begin,end) :
 end = (end + begin)//2
 if (end - begin) <= 1 :
 result=B[begin + 1 ] 
 elif BinSum(A,begin,end) == BinSum(B,begin,end):
 r = end - begin
 begin = end 
 end = (end + r)
 if begin == end :
 result=B[begin + 1 ] 
 return result 
def BinSum(C,begin,end):
 n = (end - begin)
 if end >= len(C): 
 end = len(C) - 1
 sum = n*((C[begin]+C[end])/2)
 return sum 
def main():
 A=[1,2,3,5,6,7,9,10,11,12,14,15]
 print ("smallest number missing is ",Missingelement(A))
if __name__ == '__main__': main()

Answer 22

Code for C, in fact, this can be used for any programming language without any change in the logic.

Logic is sum of N number is N*(N+1)/2.

int solution(int A[], int N) {
 // write your code in C99
 long long sum=0;
 long long i;
 long long Nsum=0;
 for(i=0;i<N;i++){
 sum=sum + (long long)A[i];
 }
 if (N%2==0){
 Nsum= (N+1)*((N+2)/2);
 return (int)(Nsum-sum);
 }
 else{
 Nsum= ((N+1)/2)*(N+2);
 return (int)(Nsum-sum);
 } 
}

This gave the 100/100 score.

• SirGuy: This technique only works if there is only 1 number missing from the array. This is not the case here.

Answer 23

This solution gets 100/100 on the test:

class Solution {
 public int solution(int[] A) {
 int x = 0;
 while (x < A.length) {
 // Keep swapping the values into the matching array positions.
 if (A[x] > 0 && A[x] <= A.length && A[A[x]-1] != A[x]) {
 swap(A, x, A[x] - 1);
 } else {
 x++; // Just need to increment when current element and position match.
 }
 }
 for (int y=0; y < A.length; y++) {
 // Find first element that doesn't match position.
 // Array is 0 based while numbers are 1 based.
 if (A[y] != y + 1) {
 return y + 1;
 }
 }
 return A.length + 1;
 }
 private void swap (int[] a, int i, int j) {
 int t = a[i];
 a[i] = a[j];
 a[j] = t;
 }
}

Answer 24

100% in PHP https://codility.com/demo/results/trainingKFXWKW-56V/

function solution($A){
 $A = array_unique($A);
 sort($A);
 if (empty($A)) return 1;
 if (max($A) <= 0) return 1;
 if (max($A) == 1) return 2;
 if (in_array(1, $A)) {
 $A = array_slice($A, array_search(1, $A)); // from 0 to the end
 array_unshift($A, 0); // Explanation 6a
 if ( max($A) == array_search(max($A), $A)) return max($A) + 1; // Explanation 6b
 for ($i = 1; $i <= count($A); $i++){
 if ($A[$i] != $i) return $i; // Explanation 6c
 }
 } else {
 return 1;
 }
}

// Explanation

1. remove all duplicates
2. sort from min to max
3. if the array is empty return 1
4. if max of array is zero or less, return 1
5. if max of array is 1, return 2 // next positive integer
6. all other cases: 6a) split the array from value 1 to the end and add 0 before first number 6b) if the value of last element of array is the max of array, then the array is ascending so we return max + 1 // next positive integer 6c) if the array is not ascending, we find a missing number by a function for: if key of element is not as value the element but it should be (A = [0=>0, 1=>1,2=>3,...]), we return the key, because we expect the key and value to be equal.

• user1438038: Please format your code properly and add some information on how this code is supposed to answer the initial question.

Answer 25

Here is my solution, it Yields 88% in evaluation- Time is O(n), Correctness 100%, Performance 75%. REMEMBER - it is possible to have an array of all negative numbers, or numbers that exceed 100,000. Most of the above solutions (with actual code) yield much lower scores, or just do not work. Others seem to be irrelevant to the Missing Integer problem presented on Codility.

int compare( const void * arg1, const void * arg2 )
{
 return *((int*)arg1) - *((int*)arg2);
}
solution( int A[], int N )
{
 // Make a copy of the original array
 // So as not to disrupt it's contents.
 int * A2 = (int*)malloc( sizeof(int) * N );
 memcpy( A2, A1, sizeof(int) * N );
 // Quick sort it.
 qsort( &A2[0], N, sizeof(int), compare );
 // Start out with a minimum of 1 (lowest positive number)
 int min = 1;
 int i = 0;
 // Skip past any negative or 0 numbers.
 while( (A2[i] < 0) && (i < N )
 {
 i++;
 }
 // A variable to tell if we found the current minimum
 int found;
 while( i < N )
 {
 // We have not yet found the current minimum
 found = 0;
 while( (A2[i] == min) && (i < N) )
 {
 // We have found the current minimum
 found = 1;
 // move past all in the array that are that minimum
 i++;
 }
 // If we are at the end of the array
 if( i == N )
 {
 // Increment min once more and get out.
 min++;
 break;
 }
 // If we found the current minimum in the array
 if( found == 1 )
 {
 // progress to the next minimum
 min++;
 }
 else
 {
 // We did not find the current minimum - it is missing
 // Get out - the current minimum is the missing one
 break;
 }
 }
 // Always free memory.
 free( A2 );
 return min;
}

Answer 26

My 100/100 solution

 public int solution(int[] A) {
 Arrays.sort(A);
 for (int i = 1; i < 1_000_000; i++) {
 if (Arrays.binarySearch(A, i) < 0){
 return i;
 }
 }
 return -1;
 }

Answer 27

 static int spn(int[] array)
 {
 int returnValue = 1;
 int currentCandidate = 2147483647;
 foreach (int item in array)
 {
 if (item > 0)
 {
 if (item < currentCandidate)
 {
 currentCandidate = item;
 }
 if (item <= returnValue)
 {
 returnValue++;
 } 
 }
 }
 return returnValue;
 }

• perror: Try to explain, at least a bit your answer. Moreover, your solution is certainly not optimal in term of worst case complexity.