27 Apr 2014

Max Repeating Number

Problem Statement: 
       Find the number with maximum frequency in the given array.


Maximum element is 2
Solution:

One of the solution to the above problem can be using the concept of hashtable, to find the max frequency element. In which it would require extra space and 2 traversals. For each number we encounter we increment the count by 1.

Now we will be still utilizing the concept of hashing without extra space. This time when ever we find a number we add a number x , which is greater than any other number in the given array to the corresponding index of the number encountered.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Find the element with maximum frequency
 * @author PRATEEK
 */
public class MaxRepeatingNumer {
 public static void main(String[] args) {

  int arr[] = { 3, 1, 3, 2, 1, 2, 2 };
  int x = 5;
  System.out.println(maxRepeatingNumer(arr, x));
 }

 private static int maxRepeatingNumer(int arr[],int k) {
  
  int i = 0, max = arr[0], result = 0;
  for (; i < arr.length; i++)
   arr[arr[i] % k] += k;

  i = 1;
  for (; i < arr.length; i++) {
   if (arr[i] > max) {
    max = arr[i];
    result = i;
   }
  }

  i = 0;
  for (; i < arr.length; i++)
   arr[i] = arr[i] % k;

  return result;
 }
}

Please comment and post your suggestions.
Happy Coding !!:)

No comments:

Post a Comment