24. Elements that appear more than n/k times

24. Elements that appear more than n/k times

Problrm link :- click here

//optimal solution to this problem is 
//using hash map
package programs;
import java.util.*;

class eleCount
{
	int element;
	int count;
}

public class Array__24
{


	static void elementsThatAppearsMoreThanNDivdedBykTimes(int arr[], int n, int k)
	{
		//creating a array of best (k-1) elements
		eleCount temp[] = new eleCount[k-1];
		
		//initializing the count all the elements of best (k-1) array to zero
		for(int i=0; i<k-1; i++)
		{
			//we just created array of objects we have to create
			//object of each and every element of the array
			eleCount element = new eleCount();
			element.element = -10;
			element.count = 0;
			temp[i] = element;
		}
		
			
		//SELSCTING BEST (k-1) ELEMENTS 
		for(int i=0; i<n; i++)
		{
			//for the if condition after for loop
			int flag = 0;
			
			//we try to push elements OR increment count if any block is 
			//                             empty OR contain the same element
			Inner1:
			for(int j=0; j<k-1; j++)
			{
				//This should be the if part or else temp[] array could be
				//filled with same elements which is the worst thing to happen
				if(temp[j].element == arr[i])
				{
					temp[j].count += 1;
					flag = 1;
					break Inner1;     //because 1 step process
				}
				
				//if temp[] array is having a free block then we will push the 
				//                                         element and increment the count
				else if(temp[j].count == 0)
				{
					temp[j].element = arr[i];
					temp[j].count += 1;
					flag = 1;
					break Inner1;     //because 1 step process
				}
			}
				
			//if neither any block is empty nor any block has the same element
			if(flag == 0)
			{
				//decrement the count of each (k-1) element in tem[]
				//this is to make impact of each and every element
				//if don't do this step always first (k-1) elements will be selected
				for(int j=0; j<k-1; j++)
					temp[j].count -= 1;
			}	
		}
		//COMPLETES SELECTION
		
		//checking which of the best (k-1) elements appeared n/k times
		for(int j=0; j<k-1; j++)
		{
			int count = 0;
			//increment count whenever we come across 
			//a element of temp[]
			for(int i=0; i<n; i++)
			{
				if( temp[j].element == arr[i] )
					count++;
			}
			if(count > (n/k))
				System.out.print(temp[j].element + "  ");
		}
	}
	
	public static void main(String[] args)
	{
		int i, n, k;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the size of the array  : ");
		n = s.nextInt();
		int array[] = new int[n];
		System.out.println("Enter the elements of the array :");
		for(i=0; i<n; i++)
			array[i] = s.nextInt();
		System.out.print("Enter an integer : ");
		k = s.nextInt();
		
		System.out.println("Given Array : ");
		print_array(array);
		
		System.out.println("\nElements which repeat more than " + n/k + " times :");
		elementsThatAppearsMoreThanNDivdedBykTimes(array, n, k);
	}

	static void print_array(int arr[])
	{
		for(int i=0; i<arr.length; i++)
			System.out.print(arr[i] + " ");
	}
}

Time complexity :- O(nk)
Space complexity :- O(k)