CareerCup

Say if k = 3, then find elements that appear n/3 times in the array which means 1/3 of the size of the array. e.g 1,1,1,2,2,3,4,4,4,4,6,7 . So here 12 elements are there and 4 appears 4 times and that is what you need to print

Question is not clear, 1/k will always be less than 1,

i gezz has map is best way to do..
Moore's voting algorithm if N/2 would have been the case !!

1/k? does not look correct logically...or else it should be k..

I think the question is k times not 1/k.

If it's k, you can easily do it using hashtables.

Sorry n/k times

answer is counting sort

here is the algo for this....
1:Sort the array.
2:initialize iCounter = 0, Value = 0;
3:for i = 0 to n-1 ( to traverse all the elements)
if (value == SortedArray[i])
{
iCounter++;
}
else
{
if( iCounter >= n/k )
{
store the variable & counter value....
increase Total number of variables by one.....(At the top of loop, you should initialize by zero)
}

iCounter = 0;
value = SortedArray[i];
}
4:Print all the variables with occurs atleast n/k time.

Here is the code in java , tested - Working

int n =12;
		int k=3;
		int m = n/k; 
		int i=0,j=0,c=0;
		int a[] = {1,1,1,2,2,3,4,4,4,4,2,6};
		
		for(i=0;i<n;i++)
		{
			c=0;
			
			for(j=0;j<n;j++)
			{
				 if(a[i]==a[j])
				 {
					 c++;
				 }
			}
			
			if(c==m)
			{
				System.out.println("The number that appears n/k = "+a[i]);
				break;
			}
		}

If we solve it using HashMap space complexity is O(n) and time complexity is O(n). If we don't use extra memory, Sort the array and linear traversal through the array to find the number. O(nLogn). Are there any other techniques which can allow the problem is solved in less than O(nLogn) without using extra space.

//n is the length, k is any number is array a, max is the max integer number in array a[]
int findNKtimesNumber(int a[], int k, int max, int n)
{
int *temp=NULL;
temp = (int *)malloc(sizeof(int)*(max+1));
memset(temp, 0, sizeof(int)*(max+1));

int i;
int rtimes = n/k;

for(i=0; i<n; i++)
{
temp[a[i]] = temp[a[i]] + 1;
}

for(i=1; i<=max; i++)
{
if(temp[i] == rtimes)
printf("%d appears %d times\n\r", i, rtimes);
}
}

def nthTimes(a:Array[Int],k: Int): Array[Int] = {
 val n = a.length/k
 a.filter(e => a.count(elem => e == elem) == n)
}

scala> val a = nthTimes(Array(8,3,5,6,1,6,9,0,-1, 78,45),5)
a: Array[Int] = Array(6, 6)

Use BST

This is variation of Majority Element Algorithm.

hi