CODEWITHSUNDEEP
java
Cass
Cass

Reputation: 77

Where is the mistake? Finding majority

I want to find the majority in array (number that appears most of the time). I have a sorted array and use these cycles:

for(int k = 1;k < length;k++)
{
    if(arr[k-1] == arr[k])
    {
        count++;
        if(count > max)
        {
            max = count;
            maxnum = arr[k-1];
        }
    } else {
        count = 0;
    }
}

or

for(int h=0;h<length;h++)
{
    for(int l=1;l<length;l++)
    {
        if(arr[h] == arr[l])
        {
            count++;
            if(count > max)
            {
                max = count;
                maxnum = arr[h];
            }
        } else count = 0;
    }
}

they are similiar. When i try them on small arrays everything seems to be ok. But on a long run array with N elements 0<=N<=500000, each element K 0<=K<=10^9 they give wrong answers. Here is solution with mistake http://ideone.com/y2gvnX. I know there are better algos to find majority but i just need to know where is my mistake.

I really can't find it :( Will really appreciate help!

Upvotes: 2

Views: 168

Answers (4)

Ted Hopp
Ted Hopp

Reputation: 234807

Your first algorithm looks correct to me. The second one (which is what your linked code uses) needs some initialization each time through the loop. Also, the inner loop does not need to start at 1 each time; it can start at h + 1:

for(int h=0; h<length; h++)
{
    count = 1; // for the element at arr[h]
    for(int l=h + 1; l<length; l++)
    {
        if(arr[h] == arr[l])
        {
            count++;
        }
    }
    if(count > max)
    {
        max = count;
        maxnum = arr[h];
    }
}

The first algorithm is much better for sorted arrays. Even for unsorted arrays, it would be cheaper to sort the array (or a copy of it) and then use the first algorithm rather than use the second.

Note that if there are ties (such as for the array [1, 1, 2, 2, 3] as per @Rohit's comment), this will find the first value (in the sort order) that has the maximum count.

Upvotes: 0

David Schwartz
David Schwartz

Reputation: 182769

Your first algorithm only makes sense if the array is sorted.

Your second algorithm just sets count to zero in the wrong place. You want to set count to zero before you enter the inner for loop.

 for(int h=0;h<length;h++)
 {
  count = 0;
  for(int l=0;l<length;l++)
  {
   if(arr[h] == arr[l])
   {
    count++;
    if(count > max)
    {
     max = count;
     maxnum = arr[h];
    }
   }
  }
 }

Also, you don't need to check count each time in the inner loop.

 max = 0;
 for(int h=0;h<length;h++)
 {
  count = 0;
  for(int l=0;l<length;l++)
  {
   if(arr[h] == arr[l])
    count++;
  }
  if(count > max)
  {
   max = count;
   maxnum = arr[h];
  }
 }

Upvotes: 0

Rohit Jain
Rohit Jain

Reputation: 213261

First of all, you should use the first algorithm, as your array is sorted. 2nd algorithm runs through the array twice unnecessarily.

Now your first algorithm is almost correct, but it has two problems: -

  • The first problem is you are setting count = 0, in else part, rather it should be set to 1. Because every element comes at least once.
  • Secondly, you don't need to set max every time in your if. Just increment count, till the if-condition is satisfied, and as soon as condition fails, check for the current count with current max, and reset the current max accordingly.

This way, your max will not be checked on every iteration, but only when a mismatch is found.

So, you can try out this code: -

    // initialize `count = 1`, and `maxnum = Integer.MIN_VALUE`.
    int count = 1;
    int max = 0;
    int maxnum = Integer.MIN_VALUE;

    for(int k = 1;k < length;k++)
     {
         if(arr[k-1] == arr[k]) {
              count++;   // Keep on increasing count till elements are equal

         } else {
             // if Condition fails, check for the current count v/s current max

             if (max < count) {   // Move this from `if` to `else`
                 max = count;
                 maxnum = arr[k - 1];
             }
             count = 1;  // Reset count to 1. As every value comes at least once.
         }
     }

Note : -

The problem with this approach is, if two numbers say - 1 and 3, comes equal number of times - which is max, then the max count will be counted for 3 (assuming that 3 comes after 1, and maxnum will contain 3 and ignore 1. But they both should be considered.

So, basically, you cannot use a for loop and maintain a count to take care of this problem.

A better way is to create a Map<Integer, Integer>, and store the count of each value in there. And then later on sort that Map on value.

Upvotes: 1

Manas Paldhe
Manas Paldhe

Reputation: 776

The error I can readily see is that if all elements are distinct, then the max at end is 0. However it has to be 1. So when you update count in "else" case, update it to 1 instead of 0, as a new element has been discovered, and its count is 1.

Upvotes: 0

Related Questions