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 :
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 34 35 36 37 38 39 | /** * 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
