Find int that appears an odd number of times in an array

Question

I am working on this task where I need to find a number that happens to appear an odd number of times in an array.

I believe I've almost done it, but if some number appears more than once in a row (like 1 in [1,1,3,1,1]), it will always return that number, no matter if it appears an odd number of times or not.

function findOdd(A) {
  var a;
  var count = 0;
  for (var i = 0; i < A.length; i++) {
    a = A[i];
    for (var l = i + 1; l < A.length; l++) {
      if (a == A[l]) {
        count++;
      }
    }
    if (!(count % 2)) {
      break;
    } else {
      count = 0;
    }
  }
  return a;
}

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

I've tried to play with adding 1 to count if [i] = [i+1], but it didn't work.

I'd expect output of findOdd([1, 1, 2, -2, 5, 2, 4, 4, -1, -2, 5]) to be -1, but it is 1. The function always returns first number that happens to be equal to next element of an array.

@NinaScholz Maybe i misunderstood, but it cant be a negative number, my output should be not count, but integer that appears an odd number of times, so count is always positive — xLyN, Jun 16 '19 at 18:59
The way you are counting is broken. When you get to the second `1` you count how many ones are after that, which is zero. So your algorithm thinks it only occurs once – an odd number of times. To do this the way you are doing it, you need to loop through the whole array in both loops. — Mark, Jun 16 '19 at 19:06
Possible duplicate of [How to count duplicate value in an array in javascript](https://stackoverflow.com/questions/19395257/how-to-count-duplicate-value-in-an-array-in-javascript) — Vlad, Jun 16 '19 at 19:09

Travis M · Answer 1 · 2019-06-16T19:22:24.227

There's no need to reset count or use a break.

function findOdd(A) {
    for (var i = 0; i < A.length; i++){
        var count = 0;
        for (var l = 0; l < A.length; l++) {
            if (A[i] === A[l]) count++;
        }
        if (count % 2 !== 0) return A[i];
    }
}

An important thing to note is that the inner loop is not starting at i+1, its starting at the 0. When A[i] matches A[l], we increment count. A number that appears an odd number of times will result in count becoming odd as well and we can return that number.

Nina Scholz · Answer 2 · 2019-06-16T20:03:40.700

0

You could count all values first and then get the value with an odd count.

function getOddCount(array) {
    var value,
        count = {},
        k;

    for (value of array) count[value] = (count[value] || 0) + 1;
    for (k in count) if (count[k] % 2) return +k;
}

console.log(getOddCount([1, 1, 3, 1, 1]));
console.log(getOddCount([1, 1, 2, -2, 5, 2, 4, 4, -1, -2, 5]));

edited Jun 16 '19 at 20:03

answered Jun 16 '19 at 19:29

Nina Scholz

376,160
25
347
392

claasic · Accepted Answer · 2019-06-16T19:56:31.640

0

The following works but I wonder how the performance compares to simply doing for loops. The complexity seems to be the same.

function findOdd(a) {
  let m = {};

  a.forEach(e => (m[e] in m) ? m[e] += 1 : m[e] = 1);
  for (k in m) {
    if (m[k] % 2 != 0) return k;
  }
}

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

edited Jun 16 '19 at 19:56

answered Jun 16 '19 at 19:36

claasic

1,050
6
14

score 0 · Answer 4 · answered Aug 11 '20 at 18:38

A naive implementation would simply use an object to store the frequency of each element and then iterate over it at the end to find the element that appeared an odd amount of times.

function findOdd(arr) {
    const freq = {};
    for(const num of arr){
        freq[num] = (freq[num] || 0) + 1;
    }
    return +Object.keys(freq).find(num => freq[num] % 2 == 1);
}

A more efficient implementation could leverage the properties of the bitwise XOR (^), namely the fact that a ^ a == 0 and that the operation is commutative and associative, leading to the solution of applying XOR on each element of the array to obtain the answer.

function findOdd(arr) {
    return arr.reduce((a,c)=>a ^ c, 0);
}

Find int that appears an odd number of times in an array

4 Answers4