Find number repeated odd times in array

Question

I completed the following exercise:

You are given an array of repeating numbers. All numbers repeat in an even way, except for one. Find that odd occurring number.

function findOdd(arr){
  obj = {};

  for (var el in arr) {
    if (!obj[arr[el]]) {
      obj[arr[el]] = 1;
    } else {
      obj[arr[el]]++;
    }
  }

  for (var key in obj) {
    if(obj[key] % 2 === 1){
      obj = {'odd': key}
    }
  }
  return parseInt(obj['odd']);
}

findOdd([1,1,2,4,4,4]);

I am trying to figure out if there are better ways to implement this. A few things come to mind:

• I believe I can nest the for loops together. I'm not sure if this saves any space or is preferable styling wise.

• I re-assigned the created object in the function so it just holds the result. I figured it's a bit more readable. Should I have just returned it in the second for loop?

• The code seems 'dirty' to me. What might be another possible solution?

Answer 1

Yes dirty, buggy, and bad.

There are several problems with your code. You have undeclared variables, do not protect against iterating over unintended enumerable array properties, redundant code, inappropriate object types, and unneeded iteration.

Undeclared variable.

You use the variable obj without declaring it. It is thus created in global scope and available to any function. This can result in difficult to spot bugs and unexpected behaviour.

Always on the first use of a variable declare it with one of JavaScript's variable types var, let, or const. In this case I will not say which type to use as the variable obj is badly used and inappropriate for the situation.

Use strict

To save you from ever make this mistake again you should add to the first line of any javascript file or script tag the line

"use strict";

this will enforce some stricter parsing standards and help you avoid making mistakes such as "forgetting to declare". It also has the benefit of running your code quicker.

Which way to iterate.

There are many ways in javascript to iterate over a set of items in arrays, objects, iterable objects, and array like objects. Using built in statements for, for...in, for...of, while, do...while, and more

The one you use is about the worst for the situation. The problem with for...in is that it will iterate over all the arr/object enumerable properties, including properties that are inherited via the object's prototype.

This means you can get almost anything for each iteration, and thus need to check every item to see if it is what you intend to be handling, and if it belongs to the object or has it be inherited from another. This is just a pain, so much so I never use it.

For your code you should have used

for(const el of arr){ 

Which does what you intended without the risk of getting unknown properties.

Dont burn cycles

Good code is efficient code, with every instruction the computer executes in your code, you burn power, sucked from batteries, the grid, You chew the clients time and you extract a little more from the environment we share as a comunity.

Yes your code is trivial in the scheme of things, immeasurable, but combined millions of programmes, or with fortune on your side an app you write may end up on billions of devices, and particular parts of your code may execute trillions of times a minute. Then it matters.

Always (I digress, no rant... :P) code for efficiency, even the little bits combined matter.

Your code could have exited early as the problem states that there is only one set of odd numbers in the array. So as soon as you find the odd set, the job is over and you should exit. On average you will do a quarter as much processing overall. On average you could do up to a quarter less processing overall.

Use appropriate Objects.

You are using obj as a map, for each unique key (number) you create an entry and use the associated value to count the number of keys. Though technically not wrong javascript provides a object Map that is better suited (see rewrite)

The rewrite

If the array of numbers was known to be sorted or numbers were grouped then a different solution could be used that is more efficient, But as there is no mention of the array being sorted or numbers grouped apart from the sample data the best is to play safe and assume unsorted data.

Some may opt to sort the array to take advantage of the better solution, but the sort is expensive and would offset any benefits the more efficient method would give.

UPDATE I miss read the question and thought that counts of one were to be excluded. I have changed the code via commenting out the incorrect behaviour.

function findOdd( arr ) {
    const counts = new Map(); 
    // find each unique number and count the entries
    for (const num of arr) {
        const item = counts.get(num); // get entry with key = num
        if (item !== undefined) {     // does it exist
            counts.set(num, item + 1);          // yes count one more
        } else {
            counts.set(num, 1);       // no so add and set count at 1
        }
    }
    // all items in the array have been checked so find the first with odd count
    for (const [num, count] of counts) {
        if (/*count > 2 &&*/ count % 2) { // See update in answer re comment
            return num; // we have found what we are looking for
        }
    }
    // the problem suggests that there is always an odd set so this
    // line will never be reached.
}

Sorted version

Just for the exercise I have included the more efficient code that assumes the array of numbers is sorted or that numbers are in groups.

function findOdd (arr) {
    var i = arr.length - 1;
    var count = 1;
    var prev = arr[i];
    while (i--) {
        const current = arr[i];
        if (current !== prev) {
            if (count % 2) { return prev }  // Update remove test for count > 2
            count = 1;
        } else { count += 1 }
        prev = current;
    }
}

Which on average executes in 1/3rd the time of the other method

Answer 2

In a more functional way you can use reduce.

Code

function findOdd(arr) {
    let quantityOfNumbrs = arr.reduce((acc, current) => {
        let key = current.toString()
        if (Object.keys(acc).includes(key)) {
            return Object.assign({}, acc, acc[key] += 1);
        }
        return Object.assign({}, acc, acc[key] = 1)
    }, {})
    return Object.keys(quantityOfNumbrs).find(number => quantityOfNumbrs[number] % 2 !== 0)
}

Explanation

I reduced it to an object and store the arr value when it ocures the first time as a key in the object and initilize the quantity with one (Object.assign({}, acc, acc[key] = 1)).
If the key allredy exists (Object.keys(acc).includes(key)) it gets incremented by one (Object.assign({}, acc, acc[key] += 1))
Now you have this object and you can get all keys stored in an array to loop trough it with find and return the key if its quantity is odd (Object.keys(quantityOfNumbrs).find(number => quantityOfNumbrs[number] % 2 !== 0))

Example

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

function findOdd(arr) {
  let quantityOfNumbrs = arr.reduce((acc, current) => {
    let key = current.toString()
    if (Object.keys(acc).includes(key)) {
      return Object.assign({}, acc, acc[key] += 1);
    }
    return Object.assign({}, acc, acc[key] = 1)
  }, {})
  return Object.keys(quantityOfNumbrs).find(number => quantityOfNumbrs[number] % 2 !== 0)
}

Feedback to your code

You initilize obj without var. Now obj is global and you could manipulate it outside of findOdd..

you could add break to the second for loop or return the number because if you found the odd number you don't need to check the numbers afte it.

for (var key in obj) {
    if(obj[key] % 2 === 1){
        return obj[key]
    }
}

Answer 3

First of all, the array passed by you as findOdd method parameter has more than one number, which is "odd occuring" number: [1,1,2,4,4,4]: 2 and 4 here.

If array realy consists of one "odd occuring" number and its elements are already sorted, I would implement it by using bitwise XOR:

var arr = [1, 1, 5, 5, 6, 6, 2, 4, 4];

var findOddNumber = function(arr) {
  let occursOddTimes = 0;

  for(let idx = 0, max = arr.length; idx < max; idx++) {
    occursOddTimes = occursOddTimes^arr[idx];
  }

  return occursOddTimes;
}

console.log(findOddNumber(arr));

Answer 4

Your first loop would look better as a for...of loop, if your version supports it:

    for (const elmt of arr) {
        if (!obj[elmt]) {
            obj[elmt] = 1;
        } else {
            obj[elmt]++;
        }
    }

Here const elmt indicates that elmt will not be updated in the loop.

You code could probably just exit the function from the second loop, once the odd-occurring element is known. If you don't do that, you should perhaps handle the case of multiple odd-occurring elements more reliably.

Answer 5

I believe I can nest the for loops together? I'm not sure if this saves any space or is preferable styling wise.

That would likely increase the complexity of the code - e.g. from \$O(n)\$ to \$O(n^2)\$ - which means that it could grow exponentially slower as the size of the array increases. Thus that would not not be preferable from the point of performance. I guess it might save space if it worked properly.

I re-assigned the created object in the function so it just holds the result. I figured it's a bit more readable. Should I have just returned it in the second for loop?

"More readable" is subjective. One could argue that it might be easier to read if a separate variable was used to store the integer:

let singleNumber;
for (var key in obj) {
    if(obj[key] % 2 === 1){
        singleNumber = key;
    }
}
return singleNumber;

But then again, as has already been mentioned by others, performance can be improved by simply returning the number as soon as it is found, which eliminates the need to create/reuse a variable:

for (var key in obj) {
    if(obj[key] % 2 === 1){
        return key;

The code seems 'dirty' to me. What might be another possible solution? Obviously others have supplied an answer here, many with suggestions of simplifying the code using const, let, functional techniques like Array.reduce(), for ... of. Those are all great points (I especially am fond of the functional approaches, though am aware performance can be degraded).

Another approach similar to the code supplied by Roman is to count the occurrences of each number, and find the count where the value is 1, but without using the functional approach. See the snippet below. Comparing time to complete for the function below appears to yield less time (using console.time()) and console.timeEnd() in FF: see this jsbin. There are mixed results about the best performance of the three - The approach with Map() appears to be fastest in Chrome and Opera, while the snippet below is fastest in Firefox and MS Edge...

function findOdd(arr){
  let counts  = {};

  for (let index = 0; index < arr.length; index++) {
    counts[arr[index]] = counts[arr[index]] ? counts[arr[index]]+1:1;
  }
  for (countNumber in counts) {
    if (counts[countNumber]%2 >0) {
      return countNumber;
    }
  }
}
console.time('findOdd');
console.log('findOdd(): ',findOdd([1,1,2,4,4,4]));
console.timeEnd('findOdd');

A note about using parseInt()

If you are going to use parseInt(), it is wise to specify the radix using the second parameter - unless you are using a unique number system like hexidecimal, octal, etc. then specify 10 for decimal numbers.

Always specify this parameter to eliminate reader confusion and to guarantee predictable behavior. Different implementations produce different results when a radix is not specified, usually defaulting the value to 10.¹

return parseInt(obj['odd'], 10);

That way, if a value like 022 is entered, it isn't interpreted as the octal value (I.e. Decimal number 18).

---

¹_{https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/parseInt#Parameters}