Monday 3 February 2014

Output maximum repeating integer in an array.

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

No comments:

Post a Comment

t> UA-39527780-1 back to top