0

I am trying to complete the following challenge...

Given an array of integers, find the one that appears an odd number of times.

There will always be only one integer that appears an odd number of times.

This is my current solution, that does not work. I believe there is a logic error somewhere but I am unsure. Any alternative ways to approach the solution that are beginner friendly are welcome also.

I am fairly new to JavaScript so please go easy!

function findOdd(A) {
  for (let i = 0; i < A.length; i++) {
    let arrayCount = [];
    let num = A[i]
    for (let x = 0; x < A.length; x++)
        if (A[i] === num) {
        arrayCount.push(num);
        //console.log(arrayCount);
        i++;
        }
    if (arrayCount.length % 2 !== 0) {
      return num;
    }
  }
}

const checkList = [1, 1, 2, 2, 3, 4, 4];

console.log(findOdd(checkList));
VLAZ
  • 26,331
  • 9
  • 49
  • 67
Zoosay
  • 1
  • 1

2 Answers2

1

Since they're all numbers, you can toggle a number using Bitwise XOR:

0 ^ 1                 -->  1
0 ^ 1 ^ 1             -->  0
0 ^ 1 ^ 1 ^ 2         -->  2
0 ^ 1 ^ 1 ^ 2 ^ 2     -->  0
0 ^ 1 ^ 1 ^ 2 ^ 2 ^ 3 -->  3


const findOdd = arr => {
  let num = 0;
  for(let i of arr) {
    num ^= i;
  }
  return num;
};

console.log(findOdd([1, 1, 2, 2, 3, 4, 4]));

If you're not dealing with numbers, you can still toggle them using object keys:

const findOdd = arr => {
  const obj = {};
  
  for(let i of arr) {
    // "toggle" the element, if i exists, add it to the object, otherwise remove it
    if(obj[i]) {
      delete obj[i];
    } else {
      obj[i] = true;
    }
  }
  
  return Object.keys(obj)[0];
};

console.log(findOdd(['a', 'a', 'b', 'b', 'c', 'd', 'd']));
Hao Wu
  • 17,573
  • 6
  • 28
  • 60
  • Just headsup the XOR trick will fail for numbers over `2 ** 31 - 1` (and lower than `-(2 ** 31)` ) as the number will be more than 32 bit and bitwise operations truncate to 32 bits only. – VLAZ Nov 30 '20 at 09:52
  • As a separate note, the toggle logic in the second case is easier expressed as `obj[i] = !obj[i]` no need for `if`/`else`. Then you can take the only one where the value is `true`. – VLAZ Nov 30 '20 at 09:53
0

The problem with your approach is, you are pushing any duplicates of any number to arrayCount, and so, its length will not be the length of a single repetetive number. Here is how I would approach this:

function findOdd(A) {
  const counts = {};
  A.forEach(function (number) {
    const currentCount = counts[number];
    if (!currentCount) {
      counts[number] = 1;
    } else {
      counts[number] = currentCount + 1;
    }
  });
  
  return Object.entries(counts).find(([_, count]) => count % 2 !== 0)[0];
}

const checkList = [1, 1, 2, 2, 3, 4, 4];

console.log(findOdd(checkList));
Sagi Rika
  • 2,839
  • 1
  • 12
  • 32
  • 1
    `Object.entries(counts).forEach(function ([number, count]) { if (count % 2 !== 0) { oddCountNumber = number; });` - this is *much* shorter expressed as `Object.entries(counts).find(([, count]) => count % 2 !== 0)[0];` – VLAZ Nov 30 '20 at 09:58