Find the most common number in an array of numbers

Posted on

Problem

Exercise description:

Find the most common number in an array of numbers.

Create a software that takes an array of numbers as parameter.
The return of the function shall be the most common number.

Example:
Assume that the list is … 1, 5, 1, 3, 5, 5, 2.

The program will output 5, because this is the most common number.

Note that if there is more than one most common number, the program
will just print one of the most common numbers.

My solution (written in TypeScript):

``````let numbers: number[] = [1, 5, 1, 3, 5, 5, 2];

namespace Main {
export function searchMostCommonNumber(arr: number[] = []): number {
let current: number = 0;
let max: number = 0;
let mostCommonNumber: number = 0;
let i: number;

for (i = 0; i < arr.length - 1; i++) {
let current: number = 1;
let j: number;

for (j = i + 1; j < arr.length; j++) {
if (arr[i] === arr[j]) {
current++;
}
}

if (current > max) {
max = current;
mostCommonNumber = arr[i];
}
}

return mostCommonNumber;
}
}

console.log(Main.searchMostCommonNumber(numbers));``````

Live demo (with compiled code):

``````var numbers = [1, 5, 1, 3, 5, 5, 2];
var Main;
(function(Main) {
function searchMostCommonNumber(arr) {
if (arr === void 0) {
arr = [];
}
var current = 0;
var max = 0;
var mostCommonNumber = 0;
var i;
for (i = 0; i < arr.length - 1; i++) {
var current_1 = 1;
var j = void 0;
for (j = i + 1; j < arr.length; j++) {
if (arr[i] === arr[j]) {
current_1++;
}
}
if (current_1 > max) {
max = current_1;
mostCommonNumber = arr[i];
}
}
return mostCommonNumber;
}
Main.searchMostCommonNumber = searchMostCommonNumber;
})(Main || (Main = {}));
console.log('The most common number is :', Main.searchMostCommonNumber(numbers));``````

What do you think about my solution?

Is there a better way to accomplish the task? What would you have done differently?

Solution

For small arrays as input your script’s performance is very good. Let me show you a different approach which might especially improve readability and might also increase performance for larger inputs and multiple runs.

`.reduce()`

Instead of iterating through the elements manually, I’ve used `Array.prototype.reduce()`:

The `reduce()` method applies a function against an accumulator and each element in the array (from left to right) to reduce it to a single value.

The function has two steps now which both use `reduce()`:

1. Reduce the input into an object that holds each number and its count as key/value-pairs.
2. Reduce this object to find the key with the highest value.

``````function findMode(numbers) {
let counted = numbers.reduce((acc, curr) => {
if (curr in acc) {
acc[curr]++;
} else {
acc[curr] = 1;
}

return acc;
}, {});

let mode = Object.keys(counted).reduce((a, b) => counted[a] > counted[b] ? a : b);

return mode;
}
``````

Performance

One requested improvement was to calculate the `mode` directly in the first `reduce` call. It could look like this:

``````function findModeAlternative(numbers) {
let max = 0;
let mode = null;
let counted = numbers.reduce((acc, curr) => {
if (curr in acc) {
acc[curr]++;
} else {
acc[curr] = 1;
}

if (max < acc[curr]) {
max = acc[curr];
mode = curr;
}

return acc;
}, {});

return mode;
}
``````

Unfortunately it didn’t improve performance in Chrome and Firefox.

Then Blindman67 suggested the naive approach with this solution:

``````function findCommon(arr) {
var max = 1,
m = [],
val = arr[0],
i, x;

for(i = 0; i < arr.length; i ++) {
x = arr[i]
if (m[x]) {
++m[x] > max && (max = m[i], val = x);
} else {
m[x] = 1;
}
} return val;
}
``````

Which will increase performance significantly in Firefox, but performs about the same in Chrome. Keep in mind, that functions like `reduce`, `map` etc. come with some overhead.

Finally the approach using `map` in Gerrit0’s answer also increases the performance drastically opposed to the original.

Test

I’ve created a test, so you can check the performance of each variant yourself. The test uses two different arrays with ca. 500 elements each and runs every function 100000 times:

• test array A is kind of mixed
• test array B contains mostly one number with a few exceptions

These are the results from Chrome 61 on macOS:

• array A “findMode”: 1000ms
• array B “findMode”: 950ms
• array A “findModeAlternative”: 1200 ms
• array B “findModeAlternative”: 1100 ms
• array A “findCommon”: 930 ms
• array B “findCommon”: 960 ms
• array A “mostCommonNumber”: 1700 ms
• array B “mostCommonNumber”: 1300 ms
• array A “searchMostCommonNumber”: 12697 ms
• array B “searchMostCommonNumber”: 13400 ms

Try it yourself

Of course you can tweak the test and try different inputs etc.

The functions’s name

As this is called mode in statistics, you could use a shorter function name like `findMode()`

Unfortunately this doesn’t improve performance. This is just a personal preference

I only included the ES6 version of the script in this answer. I didn’t add the check whether the array is an array and not empty, as this will be added when compiling from TypeScript to JavaScript

My approach would be slightly different.

1. Efficiency, though your current approach is memory efficient, it is `O(n^2)` which will make it rather slow for large arrays.

2. I don’t see any reason to include a `namespace`. With module support, namespaces seem to add unnecessary complexity in most cases.

3. Scope variables properly. There’s no reason to declare `i` and `j` outside of the loops.

4. Avoid adding types where they can be inferred. `let n: number = 0` can be written as `let n = 0` and Typescript can infer the type of `n` to be `number` without needing to explicitly type it (note that for complex types it is still sometimes a good idea to explicitly state the type).

5. Returning `0` for the empty array seems odd. There is no “most common number” if there are no numbers. Granted, returning `NaN` isn’t much better (if it even is better).

Here’s how I would implement this function.

``````function mostCommonNumber(numbers: number[]): number {
let map = new Map<number, number>()
for (let num of numbers) {
map.set(num, (map.get(num) || 0) + 1)
}

let mostCommonNumber = NaN
let maxCount = -1
for (let [num, count] of map.entries()) {
if (count > maxCount) {
maxCount = count
mostCommonNumber = num
}
}

return mostCommonNumber
}
``````

Demo:

``````function mostCommonNumber(numbers) {
let map = new Map()
for (let num of numbers) {
map.set(num, (map.get(num) || 0) + 1)
}

let mostCommonNumber = NaN
let maxCount = -1
for (let [num, count] of map.entries()) {
if (count > maxCount) {
maxCount = count
mostCommonNumber = num
}
}

return mostCommonNumber
}

let tests = [
[],
[1, 2, 3, 4, 5],
[1, 2, 3, 1, 2, 3, 1],
[1, 5, 1, 3, 5, 5, 2]
]

for (let test of tests) {
console.log(`[\${test}] --> \${mostCommonNumber(test)}`)
}``````