# Dominant number in array

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• 12-01-2012, 07:40 PM
evaaa
Dominant number in array
Hi all!

I am trying to find the dominant element of an array. My idea is to scan the original array and put every individual element in another array. If there is already the element I increase a counter. When counter>Array.length/2 then it is the dominant.
This should work with any array.

my effort so far
function mainFunc() {
var result = 0;
var myArray=[4,5,6,4,2,4,5,6,7];
//result = test(myArray);
//alert("{ " + myArray + " } --> " + result);
}

function test(A) {

var tempArray = new Array;

for(var i=0;i<A.length;i++){
// 1. check if A[i] exists in tempArray
for(var j=0;j<tempArray.length;j++){
if(A[i]==tempArray[j])
{

}

}

// 2. If A[i] exists, increase counter
if(A[i]!=tempArray[])

// 3. Check if counter > A.length/2
// 4. Return A[i]

// 5. If not, add A[i] to tempArray and set counter=1
//

}

return -1;
}

I can't find a way to make the second array correctly to extract the element with the correct counter.
Any ideas?
• 12-01-2012, 07:45 PM
donna1
by dominant do you mean most common, like the Mode in maths?

The most common still might not necessarily be > half the elements.

like in 2,3,4,2,3,4,2,1
number 2 is the most common but still 3 instances are not as much as 4 which is half the array length
• 12-01-2012, 07:47 PM
evaaa
Yes exactly. I mean more times than the half
• 12-01-2012, 08:39 PM
donna1
Yes but the most common number may not be as common as half of them.
This is my effort and it finds the Mode

var i,j=0,finds=0,found;
var array = [1,4,2,3,4,1,4,2,4,4];
var temparray = new Array();
var counter = new Array();

function mode(){
for(i in array){
found=false;
for(j in temparray){
if(temparray[j]==array[i]){
counter[j]++;
found=true;}
}
if(found==false){
temparray[finds]=array[i];
counter[finds]=1;
finds++;}
}

}

mode();
var highestIndex=0;
for(j=0;j<finds;j++){
if(counter[j]>=counter[highestIndex]){
highestIndex=j;}
}

• 12-01-2012, 09:28 PM
felgall
See http://javascriptexample.net/extobjects83.php for code to find the mode that returns the value in an array (in case two or more numbers all occur the same number of times and more than any other number)
• 12-01-2012, 10:08 PM
007julien
I propose this two lines script with a backreference regular expression
Code:

```<script type="text/javascript"> //array to test var arr=[1,41,222,33,40,18,22,41,2,2,41,42,27,41,58]; var lgt=0,nmb='',str=arr.sort().join(',').replace(/(,\d+)(\1+)/g,         function(a,b){var m;if (lgt<(m=a.length/b.length)) {lgt=m;nmb=b.substr(1)}}); alert('This number '+nmb+' appaers '+lgt+' times');        </script>```
• 12-01-2012, 10:48 PM
donna1
Quote:

Originally Posted by 007julien

var lgt=0,nmb='',str=arr.sort().join(',').replace(/(,\d+)(\1+)/g,
function(a,b){var m;if (lgt<(m=a.length/b.length)) {lgt=m;nmb=b.substr(1)}});
alert('This number '+nmb+' appaers '+lgt+' times');

</script>[/CODE]

That is very clever Monsieur J, how does that work? In particular what does the replace / , \d \1 lot do? Not sure what backslashes do there?
• 12-01-2012, 11:42 PM
Old Pedant
Well, (,\d) means "find a comma followed y one or more digits."

So it will match ",2" or ",41".

The (\1+) means "find the same thing matched by (,\d) one or more times.

So if you have ",2,2,2" that expression will first find ",2" and then see that there are two more occurrences of ",2" and end up matching all of ",2,2,2".

The only flaw in this code is that if NO string is found more than once, it will report back with [b[This number appaers 0 times[/b] (of course, the word should be "appears").

It also doesn't fulfill the requirement that the number be found more than half the time, but that's easy to do in a separate test.
• 12-01-2012, 11:47 PM
007julien
An alert(arr.sort().join(',')) give the string 1,18,2,2,22,222,27,33,40,41,41,41,41,42,58 which is an alphanumeric sort (sort(function(a,b){return a-b}) will assume a numeric increasing sort).

The \1+ after the first sub-pattern (,\d+) in the regular expression /(,\d+)(\1+)/g is a back-reference (1 for first sub-pattern) which allows to match all repeated set of one comma followed by one or more digits.

Then the anonymous function is called only for the duplicated numbers
Code:

`function(a,b){var m;if (lgt<(m=a.length/b.length)) {lgt=m;nmb=b.substr(1)}}`
The first argument a is the matched pattern (for example ,2,2 and b the first sub-pattern (the first curly bracket : ,2 in this case). The count of repetitions is also a.length/b.length, we do not use the replace function (See this page for further explanations) but define lgt (for lengthsQuotient) and nmb (for one «dominant» number).

NB : Its easy to define lgt=1 and nmb=arr[0] (with a nmb=+b.substr(1) to store a number) to replace a «This number appaers 0 times» by a better «This number 1 appears 1 time» with an alert('This number '+nmb+' appears '+lgt+' time'+(1<lgt?'s':'');
It is also possible to define the half-length of the array and test only the larger values.

This script can certainly be improved. Especially, with a (,[^,]+) instead of (,\d+) to work with all kind of comma separated values to find duplicates elements...

Apologies English is not my mother tongue
• 12-01-2012, 11:49 PM
Old Pedant
WHOOPS! I am wrong! And that code is fatally flawed!

Change the array to
Code:

`var arr=[1,41,222,33,40,18,22,41,2,2,42,27,58];`
Code:

`This number 2 appears 3 times`
Reason: After sorting the array and converting it to a string, you get:
Code:

`1,18,2,2,22,222,27,33,40,41,41,42,58`
And, as I mentioned, when it sees ",2" it looks for repetitions and indeed FALSELY finds 3:
Code:

`1,18,2,2,22,222,27,33,40,41,41,42,58`
Okay...here's a small challenge: Fix that code!

HINT: The fix is nearly trivial.
• 12-01-2012, 11:53 PM
Old Pedant
Though the code is flawed in another way: If there are two sets of numbers with the same count, it only finds the first such. This, too, could be fixed.
• 12-02-2012, 12:05 AM
Old Pedant
W.T.H. This was fun.

My version that fixes both flaws. Not as compact, but easier to understand, I hope:
Code:

```<script type="text/javascript"> function zonk(a,b) {     var m = a.length / b.length;     if (lgt <= m )     {         if ( lgt < m ) { nmb = [ ]; }         lgt = m;         nmb.push( b.replace(/,/g,"") );     } } //array to test var arr=[1,41,222,33,40,18,22,41,2,2,42,27,58]; document.write('<hr/>In the array<br/>[' + arr + ']<br/>'); var lgt = 0; var nmb = [ ]; var str = arr.sort(); str = "," + str.join(',,') + "," str.replace( /(,\d+,)(\1+)/g, zonk ); document.write('the number(s) ' + nmb.join(" and ") + ' appear(s) '+lgt+' times<hr/>');        </script>```
• 12-02-2012, 12:21 AM
evaaa
Than you all,

I tried a bit harder. That's my code

function mainFunc() {
var result = 0;
var myArray=[2,4,3,3,3,5,3,5,3,3];
result = test(myArray);
alert("{ " + myArray + " } --> " + result);
}

function test(A) {

var tempArray = new Array;

for(var i=0;i<A.length;i++){
var index = -1;

// 1. check if A[i] exists in tempArray
for(var j=0;j<tempArray.length;j++){

if(A[i]==tempArray[j][0])
{
index = j;
}
}

if(index == -1)
{
tempArray.push(A[i]);
tempArray[tempArray.length-1][1] = 1;
}
else
{
tempArray[index][1]++;
if(tempArray[index][1] > A.length/2)
{
return tempArray[index][1];
}
}

}

return -1;
}

The problem is that tempArray can't get the second dimension.
I need it to be:

tempArray[[4,1],[2,1],[3,2],[5,5]....]
and when the second element of one sub-array is bigger than A.length/2 to return this element.
• 12-02-2012, 12:26 AM
007julien
A shorter script with Old Pedant observations
Code:

```var arr=[1,41,222,33,41,41,41,40,41,18,41,41,41,22,41,2,2,41,42,27,41,58]; var dominant=null,halfLength=arr.length/2,str=arr.sort().join(',').replace(/(,\d+)(\1+)(?=,)/g,         function(a,b){if (halfLength<=a.length/b.length) {dominant=+b.substr(1)}}); var msg=dominant?'Dominant number : '+dominant:'No dominant number !' alert(msg);```
EDIT : A new corrections repetition followed by a comma or a word boundary. An assertion like (\1+)(?=,|\b) matches a repetition followed by a comma or a word boundary, but does not include the comma in the match. There is never two dominant numbers !
• 12-02-2012, 12:47 AM
Old Pedant
Is *THIS* what you are after:
Code:

```<script type="text/javascript"> function findMode( arr ) {     var counts = [ ];     for ( var a = 0; a < arr.length; ++a )     {         var elem = "E" + arr[a];         if ( counts[ elem ] == null )         {             counts[ elem ] = 1;         } else {             ++counts[ elem ];         }     }     var half = 0.5 * arr.length;     for ( var elem in counts )     {         // I don't think >= half works...what if the array is simply [1,2] ?? SO I used >         if ( counts[elem] > half ) { return elem.substring(1); }     }     return "NONE"; } var atest = [ 1, 37, 3, 2, 44, 1, 99, 1 ]; document.write( "Mode of [" + atest + "] is " + findMode(atest) + "<hr>" ); atest = [ 77, 101, 191, 91, 91, 191, 191, 191, 191 ]; document.write( "Mode of [" + atest + "] is " + findMode(atest) + "<hr>" ); </script>```
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last