trjhtr

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)?

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];

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)

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]));