A codility problem asks to find the missing number in zero-indexed array A consisting of N different integers.

E.g.

  Arr[0] = 2
  Arr[1] = 3
  Arr[2] = 1
  Arr[3] = 4
  Arr[4] = 6

I previously submitted a solution that first sorts the array and then performs a forEach function returning the value +1 where the array difference between elements is more than 1, however this doesn't get the 100 points.

Is there a way to improve this?

A codility problem asks to find the missing number in zero-indexed array A consisting of N different integers.

E.g.

  Arr[0] = 2
  Arr[1] = 3
  Arr[2] = 1
  Arr[3] = 4
  Arr[4] = 6

I previously submitted a solution that first sorts the array and then performs a forEach function returning the value +1 where the array difference between elements is more than 1, however this doesn't get the 100 points.

Is there a way to improve this?

• javascript
• arrays

14 Answers 14

Here is 100% javascript solution:

function solution(A) {
    if (!A.length) return 1;
    let n = A.length + 1;
    return (n + (n * n - n) / 2) - A.reduce((a, b) => a + b);
}

We return 1 if the given array is empty, which is the missing element in an empty array.

Next we calculate the 'ordinary' series sum, assuming the first element in the series is always 1. Then we find the difference between the given array and the full series, and return it. This is the missing element.

The mathematical function I used here are series sum, and last element:

• S_n = (n/2)*(a₁ + a_n)
• a_n = a₁ + (n - 1)*d

Get 100 in correctness and performance using this function

function solution(A) {
    // write your code in JavaScript (Node.js 4.0.0)
    var size = A.length;
    var sum = (size + 1) * (size + 2) / 2;
    for (i = 0; i < size; i++) {
        sum -= A[i];
    }
    return sum;
}

Easy if you use the Gauss formula to calculate the sum of the first N consecutive numbers:

    function solution(A) {
        var np1, perfectSum, sum;

        if (!A || A.length == 0) {
            return 1;
        }

        np1 = A.length + 1;

        // Gauss formula
        perfectSum = np1 * (1 + np1) / 2;

        // Sum the numbers we have
        sum = A.reduce((prev, current) => prev + current);

        return perfectSum - sum;
    }

From the sum of first natural numbers formula we have

now since the N item for us in the task is (N+1) we substitue n with n+1 and we get

with the formula above we can calculate the sum of numbers from 1 to n+1, since in between these numbers there is the missing number, now what we can do is we can start iterating through the given array A and subtracting the array item from the sum of numbers. The ending sum is the item which was missing in the array. hence:

function solution(A) {

    var n = A.length;

    // using formula of first natural numbers 
    var sum = (n + 1) * (n + 2) / 2;

    for (var i = 0; i < n; i++) {
        sum -= A[i];
    }

    return sum;
}

No Gauss formula, only simple and plain separate for loops that give an O(N) or O(N * log(N)) and 100% score:

function solution(A) {

    if(!A.length){
        return 1; //Just because if empty this is the only one missing.
    }

    let fullSum = 0;
    let sum = 0;

    for(let i = 0; i <= A.length; i++){
        fullSum += i+1;
    }

    for(let i = 0; i < A.length; i++){
        sum += A[i];
    }    

    return fullSum - sum;

}

Try utilizing Math.min , Math.max , while loop

var Arr = [];

Arr[0] = 2
Arr[1] = 3
Arr[2] = 1
Arr[3] = 4
Arr[4] = 6

var min = Math.min.apply(Math, Arr),
  max = Math.max.apply(Math, Arr),
  n = max - 1;

while (n > min) {

  if (Arr.indexOf(n) === -1) {
    console.log(n);
    break;
  } 

  --n;

}

This should be work good:

function solution(A) {

      // Size of the A array
      const size = A.length;

      // sum of the current values
      const arrSum = A.reduce((a, b) => a + b, 0);

      // sum of all values including the missing number
      const sum = (size + 1) * (size + 2) / 2;

      // return substruction of all - current
      return (sum - arrSum);

    }

This got me 100%

function solution(A) {
if (A.length === 0 || !A) {
    return 1;
}

A.sort((a, b) => a - b);
let count = A[0];
if (count !== 1) { return 1 }
for (let i = 0; i <= A.length; i++) {
    if (A[i + 1] === count + 1) {
        count ++;
        continue
    }
    return count + 1;
}

}

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

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

My 100% JavaScript solution:

function solution(A) {

    const N = A.length;

    // use the Gauss formula
    const sumNatural = (N + 1) * (N + 2) / 2;

    // actual sum with the missing number (smaller than sumNatural above)
    const actualSum = A.reduce((sum, num) => sum += num, 0);
    
    // the difference between sums is the missing number
    return sumNatural - actualSum;

}

I wonder why there isn't any answer using a hashtable. It's obvious that we need to iterate this array from start to end. Therefore, best solution we can have is O(n). I simply map numbers, and access them with O(1) in another iteration.

If all numbers are tagged as true, it means it's either an empty array, or it doesn't contain missing number. Either way length + 1 returns the expected output.

It returns 1 for [], and it returns 3 for [1,2].

// you can write to stdout for debugging purposes, e.g.

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    let nums = new Map()
    for (let i = 0; i < A.length; i++) {
        nums[A[i]] = true;
    }

    for (let i = 1; i < A.length + 1; i++) {
        if (nums[i]) { continue; }
        else { return i;}
    }

    return A.length + 1;
}

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    const n = A.length+1
    return (n*(n+1)/2) - A.reduce((a, b) => a + b, 0)
}

Explanation:

The formula for sum of natural numbers => n(n+1)/2
where n is the last number or last nth term. In our case, n will be our array.length. But the question states that exactly one item is missing, meaning the last nth term is array.length +1.

To find the expected sum of all our natural numbers,
We can deduct the total of the available numbers (A.reduce((a, b) => a + b, 0)) from the expected sum n(n+1)/2 to arrive at the missing number.

I had the same problem with my code:

function solution(A) {
    var i, next;

    A.sort();

    next = 1;
    for (i=0; i<A.length; i++){
        if (A[i] != next) return next;
        next++;
    }

    return next;
}

Altough it scored 100% in correctness, it returned wrong answer in all the performance tests.

The same code in C receives 100% on both:

int cmpfunc (const void * a, const void * b){
   return ( *(int*)a - *(int*)b );
}

int solution(int a[], int n) {
    int i, next;

    qsort(a, n, sizeof(int), cmpfunc);

    next = 1;
    for (i=0; i<n; i++){
        if (a[i] != next) return next;
        next++;
    }

    return next;
}

I got an alternative 100% correctness/performance solution without the Gauss formula, sorting the array first instead:

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