CareerCup

Are there any limitations on input data? Most frequent is the element with maximum frequency?

Suppose array is
1 2 1 2 ... 1 2 |2 2| 1 2 ... 1 2
The most frequent element is 2, but we are not able to know this faster than in O(n).

impossible

public class MaxRepeating {

private static final int maxRepeating(int[] input, int k){
int size = input.length;
for(int index =0 ; index<size; index++){
input[input[index]%k] += k;
}

int max = input[0], result = 0;
for (int i = 1; i < size; i++)
{
if (input[i] > max)
{
max = input[i];
result = i;
}
}
return result;
}

public static void main(String[] args) {
// TODO Auto-generated method stub
int input[] = {2, 3, 3, 5, 3, 4, 1, 7, 7, 7 };
int result = maxRepeating(input, 8);
System.out.println("Maximun repeating word is -> " + result);

int x = 2%7;
System.out.println(x);

}

}

It has the same solution as find-max in an array in O(logN)

package javaapplication23;
import java.util.Scanner;
public class JavaApplication23 {
       public static void main(String[] args) {
        int freq=0,n,i,j,finfreq=0,number=0;
        int a[]=new int[30];
        Scanner in=new Scanner(System.in);
        System.out.println("enter the number of elments");
        n=in.nextInt();
        finfreq=n;
        System.out.println("enter the elments");
        for(i=0;i<n;i++)
        {
            a[i]=in.nextInt();
        }
      for(i=0;i<n;i++)
      {
        for(j=0;j<n;j++)
        {
            if(a[i]==a[j])
            {
                freq=Math.abs(i-j);
                
                
            }
        
        }
        
      if((finfreq>freq)&&(freq!=0))
      {
          finfreq=freq;
          number=a[i];
      }
    }
    if(finfreq==0||finfreq==n)
    {
       System.out.println("no element is frequent"); 
       System.exit(0);
    }    
   System.out.println("most frequent number is"); 
    System.out.println(number);
    System.out.println("with frequency");
    System.out.println(finfreq+1);
    
    }
    
    
}

Tried it with recursion, Number of times the Loop will run depends on Number of unique elements in the array.

public class MostFrequent {

	/**
	 * @param args
	 */
	static int i=0;
	public static void main(String[] args) {
		int[] intArr = {1,4,3,2,1,4,2,1,1};
		Arrays.sort(intArr);
		findMostFrequent(intArr);
	}
	
	public static void findMostFrequent(int[] arr){
		int frequencyCnt = 0, previousFrequencyCnt = 0, elemnetIndex = 0;
		while(i<arr.length){
			frequencyCnt = countFrequency(i, arr);
			if(frequencyCnt > previousFrequencyCnt){
				previousFrequencyCnt = frequencyCnt;
				elemnetIndex = i-1;
			}
		}
		System.out.println("Most Frequent Element : "+arr[elemnetIndex]);
		System.out.println("Number of times Element appeared : " + previousFrequencyCnt);
	}
	
	public static int countFrequency(int index, int[] arr){
		i++;
		if(index < arr.length-1 && arr[index]==arr[index+1]){
			return 1+ countFrequency(index + 1, arr);
		}else{
			return 1;
		}
	}
}

Do you mean by nlogn time?