CODEWITHSUNDEEP
javascript
Firstname Lastname
Firstname Lastname

Reputation: 81

missing integer codility Javascript

Write a function:

function solution(A);

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. Assume that:

• 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].

Complexity: • expected worst-case time complexity is O(N); • expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

My Answer is 100% WRONG! What is wrong with it? First let me state the obvious errors

Assumptions I made that may be wrong

my code, which works on own test cases, and works on negative numbers too, got 0%.

function solution(A) {

    // write your code in JavaScript (Node.js 0.12)
    A.sort();
    var a_length = A.length;

    for(var i = 0; i < a_length; i++){

        // if i is 0 - 1 = -1 then do not do the following
        // if i is 1 - 1 - 0 then do the follow
        // if i >= 0 then do the following
        if(i - 1 >= 0){

            // remember above there is a A.sort() so it 
            // looks like this
            // A[0] = 1
            // A[1] = 1
            // A[2] = 2
            // A[3] = 3
            // A[4] = 4
            // A[5] = 6

            // if A[1] is 1 and A[1-1 = 0] is 1 then this is 1>1 false 
            // if A[2] is 2 and A[2-1 = 1] is 1 then this is 1>1 false  
            // if A[3] is 3 and A[3-1 = 2] is 2 then this is 1>1 false  
            // if A[4] is 4 and A[4-1 = 3] is 3 then this is 1>1 false  
            // if A[5] is 6 and A[5-1 = 4] is 4 then this is 2>1 true return A[i - 1] + 1 where A[5 - 1 = 4] is 4 + 1 is 5. 5 is returned.
            if(A[i] - A[i - 1] > 1){
                return A[i - 1] + 1;
            }
        }
    }

    // this does not check for negative
    // returns the minimal positive integer (greater than 0
    // this is a return no minimal positive integer found
    return 0;
}

Everything is wrong, example test result:

simple simple test 0.072 s WRONG ANSWER got 3 expected 1

Why does it work for me and not for them.

Upvotes: 7

Views: 24543

Answers (30)

Nazariy Vlizlo
Nazariy Vlizlo

Reputation: 977

Swift 5 with 100% solution:

public func solution(_ A : inout [Int]) -> Int {
    var occurs = Array(repeating: 0, count: A.count + 1)

    for i in A {
        if (1..<occurs.count).contains(i) {
            occurs[i] += 1
        }
    }

    for i in 1..<occurs.count {
        if occurs[i] == 0 {
            return i
        }
    }
    return A.count + 1
}

Upvotes: 0

Oz Hayun
Oz Hayun

Reputation: 1

I did it like this:

function solution(A) {
  let sortedA = A.sort((a,b) => a - b);
  let minVal = 1;

  sortedA.forEach(val => {
     if(minVal === val) {
       minVal++;
     }
  })

  return minVal;
}

console.log(solution([1, 3, 6, 4, 1, 2])) // will print 5

Upvotes: 0

Hein Diez
Hein Diez

Reputation: 1

This gave me a 100% score in Javascript.

let array = [...new Set(A)].sort((a,b)=>a-b);
let missing = 1;
array.forEach(ele=>{
    if (ele===missing){
        missing++;
    } else {
        return missing;
    }
});
return missing;

Its short and direct to the point.

Upvotes: 0

Shekhar
Shekhar

Reputation: 21

This working 100% with 100% performance

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

Screenshot of result in Codility

Upvotes: 1

Mohamad Abu Kharoub
Mohamad Abu Kharoub

Reputation: 1

I've solved the problem and I got 100% score

function missingInteger(a) {
const map = {};

let largest;
for (let i = 0; i < a.length; i++) {
    const number = a[i];

    if (number <= 0) {
        continue;
    }

    if (!largest || number > largest) {
        largest = number;
    }

    map[number] = number;
}

if (!largest) {
    return 1;
}

let exists = true;
let i;
for (i = 1; i <= largest; i++) {
    if (map[i]) {
        continue;
    }

    exists = false;
    break;
}

if (!exists) {
    return i;
}

return largest + 1;
}

Upvotes: 0

Vivek Potula
Vivek Potula

Reputation: 81

No need to use sort/set:

 function solution(A) {
    var obj = {};
    var inc = 1;
    A.forEach(item=>{
        obj[item]=item;
    });
    while(inc){
        if(!obj[inc]){
            return inc;
        }
        if(inc == 100000){
            return inc + 1;
        }
        inc++;
    }
    return inc;
}

Upvotes: 0

smnth90
smnth90

Reputation: 828

As the requirement is to check if given input array is having positive numbers from 1, I will check if the numbers from 1 to given array length are present in the array or not.

Below is my solution

function solution(A) {
  
  let a;

  for(a = 1; a <= A.length; a++) {
     if(A.indexOf(a) === -1) return a;
  }
  return a;
}`

Upvotes: 0

ZeroDrive
ZeroDrive

Reputation: 1

This is my solution 100% score without sorting

function solution(A) {
  const set = new Set(A);
  let missing = 1;

  while(true) {
    if (set.has(missing)) {
        missing++;
    } else {
        break;
    }
  }

  return missing;
}

Upvotes: 0

Nithesh Narayanan
Nithesh Narayanan

Reputation: 11765

Solution 1 A solution with complexity O(N Log N)

const solution = (A) => {
    A.sort((a, b) => a-b)
    let min = 1
    for(let item of A) {
        if(min < item) {
            return min
        }
        min = (item > 0 ? item + 1 : 1)
    }
    return min
}

console.log(solution([2, 1, -1, 1, 3, 5, 6]))

Upvotes: 0

shobhit gupta
shobhit gupta

Reputation: 1

function solution(A) {
  // write your code in JavaScript (Node.js 8.9.4)
  const set = new Set();
  const N = A.length;
  let max = 0;

  A.forEach((ele) => {
    if (ele > 0) {

      set.add(ele);

      if (ele > max) {
        max = ele;
      }
    }
  });

  for (let i = 1; i < N + 1; i++) {
    if (!set.has(i)) {
      return i;
    }
  }

  return max + 1;
}

Upvotes: 0

Satyendra Kumar
Satyendra Kumar

Reputation: 63

  • First get max number of array.
  • Then iterate 1 to max number and check which number is not exist in array and return that number.
  • Else return max+1;
function solution(A) 
    {    
        var max = A.reduce(function(a, b) {
            return Math.max(a, b);
        });    
        for(var i = 1; i <= max; i++){
            if(!A.includes(i)){
                return i;
            }
        }
        if(i > max){
            return i;
        }
    }

Upvotes: 0

Sam Autrey
Sam Autrey

Reputation: 141

function solution(A) {
  const set = new Set(A);
  let i = 1;
  while (true) {
    if (!set.has(i)) return i;
    i++;
  }
}

Upvotes: 8

F&#225;bio Paiva
F&#225;bio Paiva

Reputation: 569

function solution(A) {
    const dict = {};
    let startFrom = 1;
    for (let item of A) {
        dict[item] = true;            
        // keep startFrom greater than every number already in the dictionary
        while(dict[startFrom]) {
            startFrom++;
        }
    }
    return startFrom;
}

Upvotes: 0

Nicu-Cristian Vlad
Nicu-Cristian Vlad

Reputation: 98

My final solution :

function solution(A) {
    A = [...new Set(A)];
    let min = 1;
    A.sort((x,y) => x-y);
    for (i in A) {
       if (A[i] > -1 && A[i] == min) { min ++;}
    }
return min;
}

I find it important to remove the duplicates for an array that is huge and then sort it out this way when you fund the solution the execution would stop.

test : solution([1,2,5,7,8,3,4,2,1,9,3,3,3,3,3,3,3,3,3,3,3,3,33,3,3,3,36,-2,-1,-1,6,10,12,13,13,13,13,15,14,17,10]) -> result 11;

Result

Upvotes: 4

076
076

Reputation: 31

Score 100 out of 100: 

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const B = Array.from(new Set(A)).filter(v => v > 0).sort((a,b) => a - b);
    //First create a unique Array by creating a new set, 
    //which then we filter on values greater than 0. 
    //We sort with an explicit function, 
    //otherwise our integers are converted to strings 
    //and sorting will be based on first character rather than on value

    let i = 1; //set our initial value

    for(const val of B){ //iterate over the unique values
        if(i < val){
            return i; 
            //if val is greater than i, that means the value of i was
            //not present in our  array hence we return it
        }
        i++; //if the value was present we go to the next value, hence increase by 1
    }
    return i; 
    //if we went over the whole array, that means all values were present;
    //hence the new value of i, which equals to the highest value of the array + 1 is the correct answer.
    //Since the loop would not run in case of an empty array (which due to the filter also occurs in case of negative values), 
    //the value of i is still 1 and the correct answer.
}

If you do not want to use set (for example, because you are using old ES version) you can filter like this: 

A.filter((v,i,arr) => v > 0 && arr.indexOf(v) === i)

Upvotes: 2

ImFarhad
ImFarhad

Reputation: 3189

In JavaScript

1st Solution:

function solution(A) {
  for (i = 1; i < 1000000; i++) {
    if(!A.includes(i)) return i;
  }
}

2nd Solution:

function solution(A) {
  const set = new Set(A);
  let i = 1;
  while (set.has(i)) {
    i++;
  }
  return i;
}

3rd Solution:

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

Upvotes: -1

AbdurrahmanY
AbdurrahmanY

Reputation: 883

For JavaScript try following. Test score 100/100

Detected time complexity: O(N) or O(N * log(N))

function solution(A) {
     var missingInt = 1;

    A.sort((a, b) => { return a - b; });

    for (var i = 0; i < A.length; i++) {
        if (A[i] >= (missingInt + 1)) {
            break;
        }
        if (A[i] == missingInt) {
            missingInt++;
        }

    }

    return missingInt++;
}

Upvotes: 0

user2983165
user2983165

Reputation: 11

try the following, 

let expecterNumber = 1;
        A.sort(function(a,b){
           return a - b; 
        });

        for (let i in A) {
            if (A[i] <= 0 || A[i] == A[i - 1]) continue 
            if (A[i] != expecterNumber) break

            expecterNumber++;
        }

        return expecterNumber;
}

Upvotes: 1

Bret
Bret

Reputation: 91

Several great responses here. The most succinct and elegant IMO is https://stackoverflow.com/a/54079690 by @ben_flock.

However, just want to demonstrate a slightly more "efficient" option. I.E., it doesn't have to traverse the entire array after sorting. It short-circuits as soon as possible.

const solution = (values) => {
    values.sort( (a, b) => a-b ); // sort numerically, not lexically
    let smallest = 1; // default smallest positive integer
    values.some( value => 
        // ignore negative numbers
        // find the smallest integer not in the array
        value > 0 ? (value > smallest ? true : (smallest = value + 1) && false) : false
    );

    return smallest;
}

I used Array.prototype.sort(), Array.prototype.some(), and a ternary in this answer.

Upvotes: 0

Nikola Ravic
Nikola Ravic

Reputation: 421

There is my solution with JavaScript for Codility MissingInteger (got 100/100)

function solution(A) {
    const len = A.length;
    const hash = {};
    for (let i = 0; i < len; i++) {
        // here we are making an object with all 
        // numbers in a given array as object keys and values
        // if 0 is given as possible digit we could assing 
        // hash[A[i]] = true; or any truthy value
        hash[A[i]] = A[i];
    }
    for (let i = 1; i < 1000002; i++) {
        // here we are trying to find any number 
        // between 1 and 1000001 (given constraints) 
        // which do not exists in an object
        // if the number is not in the object that's our missing one
        if(!hash[i]) return i;
    }
    return 1;
}

Upvotes: 23

Ruchir
Ruchir

Reputation: 1068

function solution(A) {
var swap = function(i, j) {
    var tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;
};
for (let i = 0; i < A.length; i++) {
    while (0 < A[i] && A[i] - 1 < A.length
            && A[i] != i + 1
            && A[i] != A[A[i] - 1]) {
        swap(i,A[i] - 1);
    }
}
for (let i = 0; i < A.length; i++) {
      if (A[i] != i + 1) {
         return i + 1;
      }
   }
return A.length + 1;
}

Here is the final solution you are looking for

Upvotes: 0

Rajesh
Rajesh

Reputation: 24915

This is the solution that I tried during my test. Not that optimized but simple enough to read.

Idea:

  • Create a loop that will start from 1 as we are only looking for positive integer
  • For every iteration, check if current number is available in array.
  • If not available, break loop.

function solution(arr) {
  let i;
  let num = 1;
  for (i = 1; i <= arr.length; i++) {
    let exists = arr.some((n) => n === i);
    if (!exists) {
      num = i;
      break;
    }
  }
  return num;
}

console.log(solution([2, 3, 4, 5, 5]))

console.log(solution([2, 3, 4, 5, 5, 1]))

Solution 2 using hashmap:

This is a more performant and more advised solution.

  • Loop over array and create a hashmap of values. This will remove duplicates and also make lookup easy.
  • Also create a variable max and compute maximum value in array.
  • Now loop from 1 to max.
    • If value is not found, return index.
    • If all values are present, return max + 1

function solution(arr) {
  let max = 0;
  const hashMap = arr.reduce((map, num) => {
    map[num] = true;
    max = max > num ? max : num;
    return map
  }, {});
  
  for(let i = 1; i <= max; i++) {
    if (!hashMap[i]) return i
  }
  return max + 1;
}

console.log(solution([2, 3, 4, 5, 5]))

console.log(solution([2, 3, 4, 5, 5, 1]))

Upvotes: 0

Rengare
Rengare

Reputation: 21

Task score: 100% Correctness: 100% Performance: 100 %

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)

    let map = {};
    A.map(x => { map[x] = x; return x });

    let result = 1;
    while (true) {
        if (!map[result]) return result;
        result++;
    };
}

Upvotes: 1

Navdeep Singh
Navdeep Singh

Reputation: 11

function solution(A){
    A.sort((a, b) => a-b);
    let int = 1;
    for(let i = 0; i < A.length; i++){

        if(A[i] > 0 && A[i] === int){
            int++;
        } else if (A[i] > 0 && A[i] > int){
            return int;
        }
    }
    return int;
}

Upvotes: 1

Nick
Nick

Reputation: 447

My JS solution got 100 across the board. Basically, I generate a new array whose keys will be the values of the original array and set each to some truthy value. This does two things: it takes the negative values out of the iteration loop of the new array, and also allows you to loop from the smallest value up and return the first index that gives you undefined.

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

Upvotes: 4

Terrence
Terrence

Reputation: 139

Using Javascript, I did this in kind of an odd way but I got 100% on task score, correctness, and performance. However, I got an O(N) or O(N*log(N)). So, I'd like to lower that down.

function solution(A){
    // remove all negative and zero 
    let positiveArray = A.filter(x => x > 0);
    // sort all positive values
    let sortedArray = positiveArray.sort((x,y) => x-y);
    // return first that doesn't appear in order
    return sortedArray.reduce((prev, next) => {
        if(next === prev){
            prev++
        }
        return prev;
    },1);
}

Upvotes: 0

Paul Laird
Paul Laird

Reputation: 1

This was my solution that scored 66% on Task Score, 100% on Correctness and only 25% on Performance. Not the most performant solution but a working one none the less.

  1. First checks to make sure the highest number in the array is over 0, if not we end there with a result of 1
  2. Loop through numbers from 1 to highest number in array
  3. If that number does not have an index in the array, that is our result
  4. If all numbers from 1 to the highest in the array are present, the next highest number is the result
const test1 = [1, 3, 6, 4, 1, 2]; // Returns 5
const test2 = [1, 2, 3]; // Returns 4
const test3 = [-1, -3]; // Returns 1

function solution(A) {
  const lowestNum = Math.min.apply(Math, A);
  const highestNum = Math.max.apply(Math, A);

  // Check highestNum to make sure it's over 0
  if (highestNum > 0) {
    // Loop through all the numbers from 1 to the highes in the array
    for (var i = 1; i < highestNum; i++) {
      // If i does not have an index in the array, that's our solution
      if (Number(A.indexOf(i)) === -1) {
        return i;
      }
    }
    // If looped through array and all have an index, the next number is our answer
    return i + 1;
  } else {
  // If highestNum is not over 0, answer is 1
    return 1;
  }
}

solution(test1);

JS Fiddle demo

Upvotes: 0

ben_flock
ben_flock

Reputation: 121

For this problem I like to start by sorting the given array. I then iterate through the sorted array with a reduce. I give the reduce an accumulator acc initially equal to 1 (that's what the 1 after the comma is for). Only when the element val is equal to the accumulator do I increment the accumulator. Otherwise, I return the accumulator as is. When I can no longer find an element in the array equal to the accumulator, that accumulator is the lowest missing positive integer.

const solution = A => {
    A.sort((a, b) => a - b);
    return A.reduce((acc, val) => acc === val ? acc + 1 : acc, 1);
}

I know this question's been around for a while but I hope this answer is useful for someone. I use Array.prototype.sort(), Array.prototype.reduce(), and a ternary in this answer. A knowledge of those patterns should give more insight into this answer.

Upvotes: 11

user3664114
user3664114

Reputation: 1

My swift 3 solution (100/100)

public func solution(_ A : inout [Int]) -> Int {
  let set = Set(A)
  var value = 1
  while true {
    if !set.contains(value) {
      return value
    }
    value += 1
  }
}

Upvotes: 0

Edward J Beckett
Edward J Beckett

Reputation: 5140

I tried to implement the JavaScript solution similar to the one I used in Java and came to realize that JavaScripts native Array.sort() was lacking performance...

I used a RadixSort implementation from @Blindman67 to sort the array and a simple loop and scored 100/100 @ O(N) or O(N * log(N)).

function solution(A) {
    A = radixSort(A);
    let min = 1;
    for (let i = 0; i <= A.length; ++i) {
      if (A[i] == min && min <= A.length) {
        min++;
      }
    }
    return min;
}

// RadixSort by: https://codereview.stackexchange.com/users/120556/blindman67
function radixSort(numbers) {
  function emptyBuckets() {          // empties buckets and adds contents back to workArray
    workArray.length = 0;
    for (i = 0; i < 10; i += 1) {   // could have used buckets forEach but this is quicker on average
      if (buckets[i].length > 0) {
        workArray.push(...buckets[i]);
        buckets[i].length = 0;
      }
    }
  }

  var i;                  // hoist declarations
  const results = [];     // array that holds the finnal sorted numbers
  const buckets = [[], [], [], [], [], [], [], [], [], []];  // buckets
  const workArray = [...numbers]; // copy the numbers
  var power = 0;                  // current digit as a power of ten
  var tenPow = 1;                 // ten to the power of power
  if (numbers.length <= 1) {        // if one or no items then dont sort
    return workArray;           // dont sort if there is no need.
  }
  // as numbers are sorted and moved to the result array the numbers
  while (workArray.length > 0) {
    for (i = 0; i < workArray.length; i += 1) { // for all numbers still being sorted
      if (workArray[i] < tenPow) {            // is the number samller than the current digit
        results.push(workArray[i]);         //Yes it is sorted then remove a put o nthe result array
      } else {
        // add to bucket. Use Math.floor and save complexity doing it in one statement line
        buckets[Math.floor(workArray[i] / tenPow) % 10].push(workArray[i]);
      }
    }
    power += 1;
    tenPow = Math.pow(10, power);
    emptyBuckets();
  }
  return results;
}

Upvotes: 0

Related Questions