'Find the smallest positive integer that does not occur in a given sequence
I was trying to solve this problem:
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 wrote the solution below which gives a low performance, however, I can't see the bug.
public static int solution(int[] A) {
Set<Integer> set = new TreeSet<>();
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 < N; i++) {
if (C[i] > 0 && C[i] <= N) {
C[i] = 0;
}
}
for (int i = 0; i < 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.
Solution 1:[1]
100% result solution in Javascript:
function solution(A) {
// only positive values, sorted
A = A.filter(x => x >= 1).sort((a, b) => a - b)
let x = 1
for(let i = 0; i < A.length; i++) {
// if we find a smaller number no need to continue, cause the array is sorted
if(x < A[i]) {
return x
}
x = A[i] + 1
}
return x
}
Solution 2:[2]
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] > 1) return smallestInt;
if (arr[arr.length - 1] <= 0) return smallestInt;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == smallestInt) {
smallestInt++;
}
}
return smallestInt;
}
}
Solution 3:[3]
Here is an efficient python solution:
def solution(A):
m = max(A)
if m < 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)
Solution 4:[4]
JS:
filterto get positive non zero numbers from A arraysortabove filtered array in ascending ordermapto iterate loop of above stored resultifto checkxis less than the current element then return- otherwise, add 1 in the current element and assign to
x
function solution(A) {
let x = 1
A.filter(x => x >= 1)
.sort((a, b) => a - b)
.map((val, i, arr) => {
if(x < arr[i]) return
x = arr[i] + 1
})
return x
}
console.log(solution([3, 4, -1, 1]));
console.log(solution([1, 2, 0]));Solution 5:[5]
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;
/*
for efficiency — no need to calculate or access the
array object’s length property per iteration
*/
int cap = A.length;
for (int i = 0; i < cap; i++){
if(A[i] == min){
min++;
}
/*
can add else if A[i] > min, break;
as suggested by punit
*/
}
/*
min = ( min <= 0 ) ? 1:min;
which means: if (min <= 0 ){
min =1} else {min = min}
you can also do:
if min <1 for better efficiency/less jumps
*/
return min;
}
}
Solution 6:[6]
For Swift 4
public func solution(_ A : inout [Int]) -> Int {
let positive = A.filter { $0 > 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 < val) {
return x
}
x = val + 1
}
return x
}
Solution 7:[7]
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 > 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.
Solution 8:[8]
I achieved 100% on this by the below solution in Python:-
def solution(A):
a=frozenset(sorted(A))
m=max(a)
if m>0:
for i in range(1,m):
if i not in a:
return i
else:
return m+1
else:
return 1
Solution 9:[9]
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
}
Solution 10:[10]
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 => x > 0).Distinct().OrderBy(x => x).ToArray();
if(positives.Count() == 0) return 1;
int prev = 0;
for(int i =0; i < positives.Count(); i++){
if(positives[i] != prev + 1){
return prev + 1;
}
prev = positives[i];
}
return positives.Last() + 1;
}
Solution 11:[11]
My answer in Ruby
def smallest_pos_integer(arr)
sorted_array = arr.select {|x| x >= 1}.sort
res = 1
for i in (0..sorted_array.length - 1)
if res < sorted_array[i]
return res
end
res = sorted_array[i] + 1
end
res
end
Solution 12:[12]
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>=0 else 0 for a in A ])
b=1
if max_A<=0:
return(1)
else:
while b in B:
b+=1
return(b)
Solution 13:[13]
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 > 0) {
b.set(i);
}
}
return b.nextClearBit(1);
}
Solution 14:[14]
JavaScript ES6 Solution:
function solution(A) {
if (!A.includes(1)) return 1;
return A.filter(a => a > 0)
.sort((a, b) => a - b)
.reduce((p, c) => c === p ? c + 1 : p, 1);
}
console.log(solution([1, 3, 6, 4, 1, 2]));
console.log(solution([1, 2, 3]));
console.log(solution([-1, -3]));
console.log(solution([4, 5, 6]));
console.log(solution([1, 2, 4]));Solution 15:[15]
Javascript solution:
function solution(A) {
A = [...new Set(A.sort( (a,b) => a-b))];
// If the initial integer is greater than 1 or the last integer is less than 1
if((A[0] > 1) || (A[A.length - 1] < 1)) return 1;
for (let i in A) {
let nextNum = A[+i+1];
if(A[i] === nextNum) continue;
if((nextNum - A[i]) !== 1) {
if(A[i] < 0 ) {
if(A.indexOf(1) !== -1) continue;
return 1;
}
return A[i] + 1;
}
}
}
Solution 16:[16]
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) => {
if (current <= 0) return accumulator
const min = current + 1
return !A.includes(min) && accumulator > 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
Solution 17:[17]
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<A.length; i++) {
if (A[i] > 0) {
set.add(A[i])
max = Math.max(max, A[i])
}
}
for (let i=1; i<max; i++) {
if (!set.has(i)) {
return i
}
}
return max+1
}
Solution 18:[18]
100% solution in Swift, I found it here, it is really beautiful than my 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]) -> 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
}
}
}
Solution 19:[19]
0. Introduction
A) Languages allowed
The codility demo test allows for solutions
written in 18 different languages: C, C++, C#, Go, Java 8, Java 11, JavaScript, Kotlin, Lua, Objective-C, Pascal, PHP, Perl, Python, Ruby, Scala, Swift 4, Visual Basic.
B) Some remarks on your question
I write the solution below which gives a low performance
There is no reason to worry about performance until you have a correct solution. Always make sure the solution is correct before you even think about how fast or slow your algorithm/code is!
expected worst-case time complexity is O(N)
Well, as the asker of the question, it is your decision what requirements should be met in an answer. But if the goal is to score 100% on the codility (performance) test, then there is no need to demand O(N). There are plenty of solutions in the answers here which are O(N log N) and not O(N), but still pass all 4 performance tests. This proves that the O(N) requirement on time complexity is unnecessarily harsh (if the sole aim is to score 100% on the codility test).
C) About the solutions presented here
All of the solutions presented here are either refactored versions of already published answers, or inspired by such answers. I have strived to
- explicitly reference each original answer/solution,
- provide a runnable jdoodle link for each solution,
- use the same 8 tests (chosen by myself) for all the solutions,
- choose solutions that score 100% (meaning 5 of 5 for correctness and 4 of 4 for performance/speed),
- make it easy to copy-paste the answers directly into the codility demo test,
- try to have some of the most used languages respresented.
1. Java: the codility test for correctness is incorrect (!)
I will use one of the existing answers to demonstrate that the codility
test for correctness is flawed for the edge case when the given array
is empty.
In an empty array, the smallest positive missing integer is clearly 1.
Agreed?
But the codility test suite seems to accept just about any answer for
the empty array.
In the code below, I deliberately return -99 for the empty array,
which is obviously incorrect.
Yet, codility gives me a 100% test score for my flawed solution. (!)
import java.util.Arrays;
/**
https://app.codility.com/demo/take-sample-test 100%
https://stackoverflow.com/a/57067307
https://jdoodle.com/a/3B0D
To run the program in a terminal window:
javac Solution.java && java Solution && rm Solution.class
Terminal command to run the combined formatter/linter:
java -jar ../../../checkstyle-8.45.1.jar -c ../../../google_checks.xml *.java
*/
public class Solution {
/** Returns the smallest positive integer missing in intArray. */
public static int solution(int[] intArray) {
if (intArray.length == 0) { // No elements at all.
return -99; // So the smallest positive missing integer is 1.
}
Arrays.sort(intArray);
// System.out.println(Arrays.toString(intArray)); // Temporarily uncomment?
if (intArray[0] >= 2) { // Smallest positive int is 2 or larger.
return 1; // Meaning smallest positive MISSING int is 1.
}
if (intArray[intArray.length - 1] <= 0) { // Biggest int is 0 or smaller.
return 1; // Again, smallest positive missing int is 1.
}
int smallestPositiveMissing = 1;
for (int i = 0; i < intArray.length; i++) {
if (intArray[i] == smallestPositiveMissing) {
smallestPositiveMissing++;
} // ^^ Stop incrementing if intArray[i] > smallestPositiveMissing. ^^
} // Because then the smallest positive missing integer has been found:
return smallestPositiveMissing;
}
/** Demo examples. --> Expected output: 1 2 3 4 1 2 3 1 (but vertically). */
public static void main(String[] args) {
System.out.println("Hello Codility Demo Test for Java, B");
int[] array1 = {-1, -3};
System.out.println(solution(array1));
int[] array2 = {1, -1};
System.out.println(solution(array2));
int[] array3 = {2, 1, 2, 5};
System.out.println(solution(array3));
int[] array4 = {3, 1, -2, 2};
System.out.println(solution(array4));
int[] array5 = {};
System.out.println(solution(array5));
int[] array6 = {1, -5, -3};
System.out.println(solution(array6));
int[] array7 = {1, 2, 4, 5};
System.out.println(solution(array7));
int[] array8 = {17, 2};
System.out.println(solution(array8));
}
}
Below is a screen dump of the result from the test.
Since the solution is wrong, of course it should not score 100%!
1
1 You can try running the test yourself at
https://app.codility.com/demo/take-sample-test.
You will have to sign up to do so.
Simply copy-paste all of the code from the snippet above.
The default is Java 8, so you won't need to change the language.
2. A JavaScript solution
Below is a JavaScript solution.
It has not been published before, but is inspired by
one of the previous answers.
/**
https://app.codility.com/demo/take-sample-test 100%
(c) Henke 2022 https://stackoverflow.com/users/9213345
https://jdoodle.com/a/3AZG
To run the program in a terminal window:
node CodilityDemoJS3.js
Terminal command to run the combined formatter/linter:
standard CodilityDemoJS3.js
https://github.com/standard/standard
*/
function solution (A) {
/// Returns the smallest positive integer missing in the array A.
let smallestMissing = 1
// In the following .reduce(), the only interest is in `smallestMissing`.
// I arbitrarily return '-9' because I don't care about the return value.
A.filter(x => x > 0).sort((a, b) => a - b).reduce((accumulator, item) => {
if (smallestMissing < item) return -9 // Found before end of the array.
smallestMissing = item + 1
return -9 // Found at the end of the array.
}, 1)
return smallestMissing
}
// Demo examples. --> Expected output: 1 2 3 4 1 2 3 1 (but vertically).
// Note! The following lines need to be left out when running the
// Codility Demo Test at https://app.codility.com/demo/take-sample-test :
console.log('Hello Codility Demo Test for JavaScript, 3.')
console.log(solution([-1, -3]))
console.log(solution([1, -1]))
console.log(solution([2, 1, 2, 5]))
console.log(solution([3, 1, -2, 2]))
console.log(solution([]))
console.log(solution([1, -5, -3]))
console.log(solution([1, 2, 4, 5]))
console.log(solution([17, 2])).as-console-wrapper { max-height: 100% !important; top: 0; }3. A Python solution
Python has come to compete with Java as one of the most used programming languages worldwide. So here is a Python solution. The code below is a slightly rewritten version of this answer.
#!/usr/bin/env python3
'''
https://app.codility.com/demo/take-sample-test 100%
https://stackoverflow.com/a/58980724
https://jdoodle.com/a/3B0k
To run the program in a terminal window:
python codility_demo_python_a.py
Command in the terminal window to run the linter:
py -m pylint codility_demo_python_a.py
https://pypi.org/project/pylint/
Dito for autopep8 formatting:
autopep8 codility_demo_python_a.py --in-place
https://pypi.org/project/autopep8/
'''
def solution(int_array):
'''
Returns the smallest positive integer missing in int_array.
'''
max_elem = max(int_array, default=0)
if max_elem < 1:
return 1
int_array = set(int_array) # Reusing int_array although now a set
# print(int_array) # <- Temporarily uncomment at line beginning
all_ints = set(range(1, max_elem + 1))
diff_set = all_ints - int_array
if len(diff_set) == 0:
return max_elem + 1
return min(diff_set)
# Demo examples. --> Expected output: 1 2 3 4 1 2 3 1 (but vertically).
# Note! The following lines need to be commented out when running the
# Codility Demo Test at https://app.codility.com/demo/take-sample-test :
print('Hello Codility Demo Test for Python3, a.')
print(solution([-1, -3]))
print(solution([1, -1]))
print(solution([2, 1, 2, 5]))
print(solution([3, 1, -2, 2]))
print(solution([]))
print(solution([1, -5, -3]))
print(solution([1, 2, 4, 5]))
print(solution([17, 2]))
4. A C# solution
Here is a solution for C#.
This solution too is inspired by a previous answer.
using System;
using System.Linq;
/// https://app.codility.com/demo/take-sample-test 100%
/// (c) 2021 Henke, https://stackoverflow.com/users/9213345
/// https://jdoodle.com/a/3B0Z
/// To initialize the program in a terminal window, only ONCE:
/// dotnet new console -o codilityDemoC#-2 && cd codilityDemoC#-2
/// To run the program in a terminal window:
/// dotnet run && rm -rf obj && rm -rf bin
/// Terminal command to run 'dotnet-format':
/// dotnet-format --include DemoC#_2.cs && rm -rf obj && rm -rf bin
public class Solution {
/// Returns the smallest positive integer missing in intArray.
public int solution(int[] intArray) {
var sortedSet =
intArray.Where(x => x > 0).Distinct().OrderBy(x => x).ToArray();
// Console.WriteLine("[" + string.Join(",", sortedSet) + "]"); // Uncomment?
if (sortedSet.Length == 0) return 1; // The set is empty.
int smallestMissing = 1;
for (int i = 0; i < sortedSet.Length; i++) {
if (smallestMissing < sortedSet[i]) break; // The answer has been found.
smallestMissing = sortedSet[i] + 1;
} // Coming here means all of `sortedSet` had to be traversed.
return smallestMissing;
}
/// Demo examples. --> Expected output: 1 2 3 4 1 2 3 1 (but vertically).
/// NOTE! The code below must be removed before running the codility test.
static void Main(string[] args) {
Console.WriteLine("Hello Codility Demo Test for C#, 2.");
int[] array1 = { -1, -3 };
Console.WriteLine((new Solution()).solution(array1));
int[] array2 = { 1, -1 };
Console.WriteLine((new Solution()).solution(array2));
int[] array3 = { 2, 1, 2, 5 };
Console.WriteLine((new Solution()).solution(array3));
int[] array4 = { 3, 1, -2, 2 };
Console.WriteLine((new Solution()).solution(array4));
int[] array5 = { };
Console.WriteLine((new Solution()).solution(array5));
int[] array6 = { 1, -5, -3 };
Console.WriteLine((new Solution()).solution(array6));
int[] array7 = { 1, 2, 4, 5 };
Console.WriteLine((new Solution()).solution(array7));
int[] array8 = { 17, 2 };
Console.WriteLine((new Solution()).solution(array8));
}
}
5. A Swift solution
Here is a solution for Swift, taken from this answer.
/**
https://app.codility.com/demo/take-sample-test 100%
https://stackoverflow.com/a/57063839
https://www.jdoodle.com/a/4ny5
*/
public func solution(_ A : inout [Int]) -> Int {
/// Returns the smallest positive integer missing in the array A.
let positiveSortedInts = A.filter { $0 > 0 }.sorted()
// print(positiveSortedInts) // <- Temporarily uncomment at line beginning
var smallestMissingPositiveInt = 1
for elem in positiveSortedInts{
// if(elem > smallestMissingPositiveInt) then the answer has been found!
if(elem > smallestMissingPositiveInt) { return smallestMissingPositiveInt }
smallestMissingPositiveInt = elem + 1
}
return smallestMissingPositiveInt // This is if the whole array was traversed.
}
// Demo examples. --> Expected output: 1 2 3 4 1 2 3 1 (but vertically).
// Note! The following lines need to be left out when running the
// Codility Demo Test at https://app.codility.com/demo/take-sample-test :
print("Hello Codility Demo Test for Swift 4, A.")
var array1 = [-1, -3]
print(solution(&array1))
var array2 = [1, -1]
print(solution(&array2))
var array3 = [2, 1, 2, 5]
print(solution(&array3))
var array4 = [3, 1, -2, 2]
print(solution(&array4))
var array5 = [] as [Int]
print(solution(&array5))
var array6 = [1, -5, -3]
print(solution(&array6))
var array7 = [1, 2, 4, 5]
print(solution(&array7))
var array8 = [17, 2]
print(solution(&array8))
6. A PHP solution
Here is a solution for PHP, taken from this answer.
/**
https://app.codility.com/demo/take-sample-test 100%
https://stackoverflow.com/a/60535808
https://www.jdoodle.com/a/4nB0
*/
function solution($A) {
$smallestMissingPositiveInt = 1;
sort($A);
foreach($A as $elem){
if($elem <=0) continue;
if($smallestMissingPositiveInt < $elem) return $smallestMissingPositiveInt;
else $smallestMissingPositiveInt = $elem + 1;
}
return $smallestMissingPositiveInt;
}
// Demo examples. --> Expected output: 1 2 3 4 1 2 3 1 .
// Note! The following lines need to be left out when running the
// Codility Demo Test at https://app.codility.com/demo/take-sample-test :
echo "Hello Codility Demo Test for PHP, 1.\n";
echo solution([-1, -3]) . " ";
echo solution([1, -1]) . " ";
echo solution([2, 1, 2, 5]) . " ";
echo solution([3, 1, -2, 2]) . " ";
echo solution([]) . " ";
echo solution([1, -5, -3]) . " ";
echo solution([1, 2, 4, 5]) . " ";
echo solution([17, 2]) . " ";
Reference
Solution 20:[20]
My solution having 100% result in codility with Swift 4.
func solution(_ A : [Int]) -> Int {
let positive = A.filter { $0 > 0 }.sorted()
var x = 1
for val in positive{
if(x < val) {
return x
}
x = val + 1
}
return x
}
Solution 21:[21]
My simple and (time) efficient Java solution:
import java.util.*;
class Solution {
public int solution(int[] A) {
Set<Integer> set=new TreeSet<>();
for (int x:A) {
if (x>0) {
set.add(x);
}
}
int y=1;
Iterator<Integer> it=set.iterator();
while (it.hasNext()) {
int curr=it.next();
if (curr!=y) {
return y;
}
y++;
}
return y;
}
}
Solution 22:[22]
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]) -> Int {
let B = A.filter({ element in
element > 0
}).sorted()
var result = 1
for element in B {
if element == result {
result = result + 1
} else if element > result {
break
}
}
return result
}
Solution 23:[23]
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("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
int N = A.Length;
HashSet<int> set =new HashSet<int>();
foreach (int a in A) {
if (a > 0) {
set.Add(a);
}
}
for (int i = 1; i <= N + 1; i++) {
if (!set.Contains(i)) {
return i;
}
}
return N;
}
}
Solution 24:[24]
This is for C#, it uses HashSet and Linq queries and has 100% score on Codility
public int solution(int[] A)
{
var val = new HashSet<int>(A).Where(x => x >= 1).OrderBy((y) =>y).ToArray();
var minval = 1;
for (int i = 0; i < val.Length; i++)
{
if (minval < val[i])
{
return minval;
}
minval = val[i] + 1;
}
return minval;
}
Solution 25:[25]
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>0){
if(a>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>0 && i<=N){
hashed[i-1] = 1;
}
}
for(int i = 0; i<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.
Solution 26:[26]
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 < N; i++) {
/*
* we need the absolute value for the duplicates
* */
int j = Math.abs(A[i]) - 1;
if (j >= 0 && j < N && A[j] > 0) {
C[j] = -A[j];
}
}
for (int i = 0; i < N; i++) {
if (C[i] == 0) {
return i + 1;
}
}
return N + 1;
}
Solution 27:[27]
//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;
}
}
Solution 28:[28]
<JAVA> Try this code-
private int solution(int[] A) {//Our original array
int m = Arrays.stream(A).max().getAsInt(); //Storing maximum value
if (m < 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 < A.length; i++) {
if (A[i] > 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 < 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
Solution 29:[29]
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, anderase, while the second one takes advantage ofstd::setand 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, thenvec.at(i-1)+1is the smallest missing positive integer. - If
vec.at(i) != i+1is 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<int>& 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<int> s(rawVec.begin(), rawVec.end());
// rawVec.assign(s.begin(), s.end());
//Remove all ints < 1
vector<int> vec;
vec.reserve(rawVec.size());
for(const auto& el : rawVec)
{
if(el>0)
vec.push_back(el);
}
//Edge case: All ints were < 1 or all ints were > 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<vec.size(); ++i)
{
if(vec.at(i) != i+1)
return vec.at(i-1)+1;
}
return vec.back()+1;
}
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow