1
\$\begingroup\$

I am trying to solve the following exercise using Javascript:

A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

For example, in array A such that:

  A[0] = 9  A[1] = 3  A[2] = 9
  A[3] = 3  A[4] = 9  A[5] = 7
  A[6] = 9

the elements at indexes 0 and 2 have value 9, the elements at indexes 1 and 3 have value 3, the elements at indexes 4 and 6 have value 9, the element at index 5 has value 7 and is unpaired.

I have written the following code.

function solution(A) {        
    var pop;

    if(!A.length)
        return 0;

    while(A.length){
        pop = A.shift();            
        let pos = A.indexOf(pop);
        if(pos >-1){
            A.splice(pos,1);                
        } else {
            return pop
        }
    }
    return pop;
}

The correctness seems to be fine but it fails the performance test. The order shown is O(N**2).

  • Any explanation why it shows exponential timing (I have not used any nested loops)?
  • Any suggestions on what would be the optimized code which will run on O(N) having space complexity O(1)?
\$\endgroup\$
1
\$\begingroup\$

Any explanation why it shows exponential timing (I have not used any nested loops)?

Inside the while loop you have A.indexOf(pop); which is the second inner loop. It iterates over each item until it finds the match. You can use a Set which uses a hash table to locate items.

Any suggestions on what would be the optimized code which will run on O(N)?

Use a Set. For each item first check the set, if its there remove it and the item, else add the item to the set and move to the next item. When done you should have one item remaining in the set, that will be the odd one out.

function findOdd(arr){
    const found = new Set(); 
    while (arr.length > 0) {
        const val = arr.pop(); // or use shift

        // if val in found remove it from the set
        if (found.has(val)) { found.delete(val) }
        else { found.add(val) } // else add it to the set
    }
    return [...found.values()][0];
}
\$\endgroup\$
  • \$\begingroup\$ Elegant solution! Can you confirm the worst case space complexity of this? I think it is O(1) (not counting the storage required for input arguments) - correct me if I'm wrong. \$\endgroup\$ – Anirban Bera Jul 13 '18 at 4:26
  • \$\begingroup\$ @AnirbanBera Sorry O(n) space for hash tables. See wiki en.wikipedia.org/wiki/Hash_table \$\endgroup\$ – Blindman67 Jul 13 '18 at 5:01
  • \$\begingroup\$ // if val in found remove it from the set comment is useless. \$\endgroup\$ – Stexxe Jul 13 '18 at 11:37
2
\$\begingroup\$

The solution with an O(N) time complexity with O(1) space is a little bit hacky. The solution is to xor each number together. some important properties of xor are:

  1. xor of two identical numbers is zero.
  2. xor of any number and zero is the number.
  3. xor is commutative.
  4. xor is associative.

example:

A = [9, 3, 9, 3, 9, 7, 9]

the solution to this example is:

  (((((9^3)^9)^3)^9)^7)^9
= 9^3^9^3^9^7^9              (4)
= 9^9^9^9^3^3^7              (3)
= (9^9)^(9^9)^(3^3)^7        (3)
= 0^0^0^7                    (1)
= 7                          (2)
\$\endgroup\$
1
\$\begingroup\$

We can find unpaired number by sorting array of integers and searching for one, which has no adjacent with same value. My suggested solution:

const nextIsDifferent = (el, index, arr) => ((index + 1) % 2 === 1 && el !== arr[index + 1]);
const findUnpaired = (arr) => arr.sort().find(nextIsDifferent);

console.log(findUnpaired([9, 3, 9, 3, 9, 7, 9]));
\$\endgroup\$
  • \$\begingroup\$ You have supplied an alternative solution, without saying how or why it is better. If you could add some details, this would make a nice answer. \$\endgroup\$ – Graipher Jul 13 '18 at 12:33
  • \$\begingroup\$ This is also a nice solution. Can you please elaborate on the time complexity of it? will it be O(N) or O(NlogN) <for sorting>? \$\endgroup\$ – Anirban Bera Jul 13 '18 at 15:58
  • \$\begingroup\$ I think it's O(NlogN) \$\endgroup\$ – Stexxe Jul 13 '18 at 20:41
  • \$\begingroup\$ I did this in Codility lesson, albeit I was using C#. At first, I used LINQ but the performance was bad,I changed to this algo and got 100% score. \$\endgroup\$ – Rosdi Kasim Feb 5 at 14:16
0
\$\begingroup\$

Initially I came up with this solution:

function solution(A) {
    let arr = [];

    for (let int of A) {
        if (arr[int] === false) {
            arr[int] = true
        } else (
            // only one element found so far
            arr[int] = false
        )
    }
    return arr.indexOf(false);
}

However, it is either O(n) or O(nlog(n)) on Codility, and fails the last performance test.

@Peter's approach seems like the best.

I cheated and modified from this Java solution:

class Solution {
    public int solution(int[] A) {
        int result = 0;
        for (int x : A) result ^= x;
        return result;
    }
}

to get this solution, which has a 100% task score on Codility (with both 100% correctness and a 100% performance score; try it yourself):

function solution(A) {
    var result = 0;
    for (let int of A) {
        result ^= int;
    }
    return result;
}

The code in the question gets a 100% correctness score, but the performance score is only 25%.

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer. \$\endgroup\$ – Toby Speight Feb 28 at 9:57
  • \$\begingroup\$ Thanks, I added a note at the end of the answer. \$\endgroup\$ – James Ray Feb 28 at 10:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.