Solution to Missing-Integer by codility | Code Says
Question: https://codility.com/demo/take-sample-test/missing_integer
https://github.com/yiqin/Codility-Practice/blob/master/MissingInteger.java
Space optimization:
public int solution(int[] A) {
int positiveCount = 0;
for(int i=0; i< A.length; i++) {
positiveCount++;
}
int[] B = new int[positiveCount];
for(int i=0; i<A.length; i++) {
if(A[i]<=A.length && A[i]>0) {
B[A[i]-1]=1;
}
}
int min = B.length+1;
for(int i=0; i<B.length; i++) {
if(B[i]==0) {
// min = B[i]+1;
min = i+1;
break;
}
}
return min;
}
http://www.martinkysel.com/codility-missinginteger-solution/
http://codility-lessons.blogspot.com/2014/07/lesson-2-missing-integers.html
Read full article from Solution to Missing-Integer by codility | Code Says
Question: https://codility.com/demo/take-sample-test/missing_integer
Write a function:
int solution(int A[], int N);
that, given a non-empty zero-indexed array A of N integers, returns the minimal positive integer (greater than 0) that does not occur in A.
For example, given:
A[0] = 1 A[1] = 3 A[2] = 6 A[3] = 4 A[4] = 1 A[5] = 2
the function should return 5.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
def solution(A):
''' Solve it with Pigeonhole principle.
There are N integers in the input. So for the
first N+1 positive integers, at least one of
them must be missing.
'''
# We only care about the first N+1 positive integers.
# occurrence[i] is for the integer i+1.
occurrence = [False] * (len(A) + 1)
for item in A:
if 1 <= item <= len(A) + 1:
occurrence[item-1] = True
# Find out the missing minimal positive integer.
for index in xrange(len(A) + 1):
if occurrence[index] == False:
return index + 1
raise Exception("Should never be here.")
return -1
|
https://github.com/yiqin/Codility-Practice/blob/master/MissingInteger.java
Space optimization:
public int solution(int[] A) {
int positiveCount = 0;
for(int i=0; i< A.length; i++) {
positiveCount++;
}
int[] B = new int[positiveCount];
for(int i=0; i<A.length; i++) {
if(A[i]<=A.length && A[i]>0) {
B[A[i]-1]=1;
}
}
int min = B.length+1;
for(int i=0; i<B.length; i++) {
if(B[i]==0) {
// min = B[i]+1;
min = i+1;
break;
}
}
return min;
}
http://www.martinkysel.com/codility-missinginteger-solution/
http://codility-lessons.blogspot.com/2014/07/lesson-2-missing-integers.html
Read full article from Solution to Missing-Integer by codility | Code Says
