CODEWITHSUNDEEP
javascriptalgorithm
AndrewNeedsHelp
AndrewNeedsHelp

Reputation: 415

Finding the integer that appears an odd number of times

Question

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.

My Attempt

function findOdd(A) {
  let newArr = A.sort();
  let altArr = [];
  let count = 0;
  let firstCharacter = newArr[0];

  for (let i = 0; i < newArr.length; i++) {
    if (newArr[i] == firstCharacter) {
      count++;

    } else {
      let subArr = newArr.slice(newArr[0], count);
      console.log(subArr);
      altArr.push(subArr);
      count = 0;
      firstCharacter = newArr[i];
    }
  }
  for (let i = 0; i < altArr.length; i++) {
    if (altArr[i].length % 2 != 0) {
      return altArr[i][0];
    }
  }
}


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

Problem

I used console logs which showed me that the slices are returning an empty array Which I think is why this algorithm is broken. But why does it return an empty array? And is there any other mistakes i have missed?

Upvotes: 1

Views: 1729

Answers (3)

Unmitigated
Unmitigated

Reputation: 89324

You are making this problem much more complicated than it actually is. 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, a ^ 0 == a, 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);
}

Upvotes: 6

Nina Scholz
Nina Scholz

Reputation: 386654

After sorting, you could take a single loop and check the value against the last value (initialize without a value).

function findOdd(array) {
    let count = 0;
    let last;

    array.sort();

    for (let i = 0; i < array.length; i++) {
        if (array[i] === last) {
            count++;
            continue;
        } 
        if (count % 2) return last;
        last = array[i];
        count = 1;
    }
    return last;
}

console.log(findOdd([20, 1, -1, 2, -2, 3, 3, 5, 5, 1, 2, 4, 20, 4, -1, -2, 5]))
.as-console-wrapper { max-height: 100% !important; top: 0; }

Upvotes: 0

Song
Song

Reputation: 750

newArr.slice(newArr[0], count); slice takes 2 parameters and they need to be index, not an actual value. So the above code is definitely not correct. I think you can use dictionary to simplify this algorithm. Here is my approach.

function findOdd(A) {
    const appearances = {};
    A.forEach(val => {
        appearances[val] = (appearances[val] || 0) + 1;
    });
    const oddNumbers = Object.keys(appearances).filter(key => appearances[key] % 2 != 0);
    return oddNumbers.length > 0 ? oddNumbers[0] : NaN;
}

Upvotes: 1

Related Questions