# Finding numbers with odd frequency in an array

Below is my Code, I want to know ways to improve it.

const findOdd = (A) => {

newObj={};

A.filter((cur,index) =>{
return A.indexOf(cur)===index;
}).forEach((cur) =>{
newObj[cur] = 0
for(let i = 0; i<A.length; i++) if(cur === A[i]) newObj[cur] +=1;
});

const keys = Object.keys(newObj)
key = keys.filter(cur => newObj[cur] % 2 !== 0)

return parseInt(key[0]);
}


Test Case : A = [1,1,2,-2,5,2,4,4,-1,-2,5]

Output = -1

Edit : I am trying to create a list of distinct elements at first then add them to an object with key as elements and value as their frequency, then finally finding the keys with odd frequencies.

• What are odd occurrences? It is not clear from the example, and your propensity for skipping newlines makes it unclear from the code as well. Sep 8, 2020 at 11:50
• What does your code do and what do you want from us? Remember: in a "real world" code review, the code review would be held with a specific purpose (improving throughput, reducing memory usage, find security holes, improve readability, etc.) and you would be in the room with us, walking us through your code line-by-line explaining every choice, every variable, every function. On this website, all we have is your question, so you need to make sure that all the information that we would normally get during the review is part of the question. Sep 8, 2020 at 12:15
• @konijn I mean if frequency of a number is odd. Sep 8, 2020 at 12:24
• @JörgWMittag I am trying to create a list of distinct elements at first then add them to an object with key as elements and value as their frequency. then finally finding the keys with odd frequencies. Sep 8, 2020 at 12:30

Undeclared variables You aren't declaring your newObj variable or your key variable. This will either implicitly create properties on the global object, or throw an error in strict mode. Both should be avoided. Always declare your variables (with const, or let when const isn't usable) before using them for the first time. Eg, change newObj={}; to const newObj = {};.

Algorithm complexity Your current approach is pretty computationally expensive. .indexOf will iterate through all elements of the array until it finds a match, or until it reaches the end of the array. .filter will iterate through all elements of an array. With an .indexOf inside a .filter, the computational complexity is O(n ^ 2). (For example, given an array of 30 items, you can expect to have to carry out 900 times more operations than an array with only 1 item, worst-case.) That's not very good.

Inside the forEach, you again iterate over every element of the array, resulting in another operation of O(n ^ 2) complexity.

To reduce the overall complexity of the whole findOdd function to O(n), iterate over the input array only once, and inside the loop, either create a property on the object, or increment the existing property. (See snippet below for a demo.)

Variable names You have variable names A and newObj. At a glance, these are not very informative. Better to give them names that represent what they contain so you can understand them at a glance, such as inputNumbers and occurrencesByNumber. Also, the variable named key isn't actually a key - it's an array of keys. Better to make it plural: keys.

Semicolons Sometimes you're using semicolons, sometimes you aren't. Unless you're an expert, I'd recommend using semicolons, else you may occasionally run into hard-to-understand errors due to Automatic Semicolon Insertion. I'd highly a linter (not just for semicolons, but for many ways to prompt you to correct potential bugs before they turn into errors, and to enforce a consistent code style)

Iterating over an object You collect the keys using Object.keys, then you iterate over the value at each key by accessing the property of the object: newObj[cur]. If you want to iterate over keys and values at once, you can consider using Object.entries instead.

.find or .filter? If the objective is to

then finally finding the keys with odd frequencies.

then

return parseInt(key[0])


is not the right approach, since it'll return only the first element of the array. If you want only one match to be returned, use .find above instead of .filter, so that it ends as soon as a match is found. If you want more than one match to be found, return the array of keys/entries, mapped to numbers.

Demo implementing these fixes:

const findOdd = (inputNumbers) => {
const occurrencesByNumber = {};
for (const number of inputNumbers) {
occurrencesByNumber[number] = (occurrencesByNumber[number] || 0) + 1;
}
return Object.entries(occurrencesByNumber)
.filter(([, occurrences]) => occurrences % 2 === 1)
.map(([numberKey]) => Number(numberKey));
};

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

The feedback of CertainPerformance is already solid. Some minor extra points;

• Avoid fat arrow syntax unless you write an inline function (easier to read)
• findOdd is an unfortunate name, how about findOddCounts, which is still a bit awkward but is definitely more evocative
• The nice thing about odd/even is that they follow each other up, you dont have to track the count, you could just track the parities.

All this was really just an excuse to write this;

function findOddCounts(list){
const parities = {};
list.forEach(n => parities[n] = !parities[n]);
return Object.keys(parities).filter(n => parities[n]).map(n => n*1);
}

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

//This inspired slepic to mention using a set which could look like this:

function findOddCounts(list){
const set = new Set();
list.forEach(n => set.has(n) ? set.delete(n) : set.add(n));
return [...set.keys()];
}

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

/* There is no need to coerce the output of set.keys(),
though jshint will not like the abuse of ternary
and without the ternary it just looks worse to me */

• It might be better to use Set, if has then remove else set. The set will contain exactly the elements that occured odd number of times. No type juggling, no filtering... Sep 9, 2020 at 18:25
• Great idea, I always seem to forget about Set Sep 9, 2020 at 20:36
• @slepic Or set.delete(n) || set.add(n) (without has)? Sep 9, 2020 at 23:58
• @superbrain yeah i guess that's also possible :) Sep 10, 2020 at 3:22
• That Set solution is such a nice one it made me smile, as I was about to write “it can't work” twice already until the realization hit me. It is also really efficient (one could also reduce straight into it, but that's a matter of taste I suppose). Sep 10, 2020 at 16:39