Question :
Given array of N integers ranging from 0 to N-1. Output maximum repeating integer. Use only O(1) memory.
Idea :
Idea is to iterate over the array. Computer array[i]%N which will give back the value in array[i]. Now use this computed value as index and add N to the value at that index. Do this for all elements in the array. Return index of the maximum element in the array. If we have a number say X<N appearing M times(Maximum) then we simply add N value M times to the value present at index X which makes it maximum.
Solution :
/**
* Created with IntelliJ IDEA.
* User: aniket
* Date: 3/2/14
*/
public class MaxOccurrencesFinder {
public static int findMqxOccurrenceNumber(int[] array){
int numberWithMaxOccurrence = 0;
int indexOfNumberWithMaxOccurrence = 0;
int arrayLength = array.length;
for(int i=0;i<arrayLength;i++){
array[array[i]%arrayLength] = array[array[i]%arrayLength] + arrayLength;
}
for(int i=0;i<arrayLength;i++){
if(array[i] > numberWithMaxOccurrence){
numberWithMaxOccurrence = array[i];
indexOfNumberWithMaxOccurrence = i;
}
}
return indexOfNumberWithMaxOccurrence;
}
public static void main(String args[]){
//array of length 10
//permitted values 0-9
int [] array = new int[]{4,6,1,9,2,4,9,1,4,6};
System.out.println("Max occurred number : " + MaxOccurrencesFinder.findMqxOccurrenceNumber(array));
}
}
Output :
Max occurred number :4
