CareerCup

We know that the numbers present in the array are in the range 0 to n-1.
We traverse the array from left to right and for each element ,a[i], we increment the value at the index a[i] by n. In case the value at any index is more than (n-1) then we know that the index's value has been incremented because that index is the value we have already encountered while traversing the array. To know the exact value at that index we take mod of n and get the original value. Again considering that value say v as the index, we increment the value at the index v by n.
After we are done traversing once, we again traverse the array from left to right and find out which index's value has been incremented maximum times. We can do that by dividing the value by n. We can restore the original value of the array by taking mod of n for each element.

#include <iostream>
using namespace std;

int getMaxRepeatedNum(int *a,int m,int n)
{
int i,k,max=0,p=0;
for(i=0;i<m;i++)
{
k=a[i]%n;
a[k]+=n;
}
/* for(i=0;i<m;i++) cout<<a[i]<<"\t";
cout<<endl;*/
for(i=0;i<m;i++)
{
k=a[i]/n;
a[i]=a[i]%n;
if(k>max)
{
max=k;
p=i;
}
}
/* for(i=0;i<m;i++) cout<<a[i]<<"\t";
cout<<endl;*/
return p;
}

int main() {
int a[]={3,1,6,3,2,0,4,4,3,1,3,0,2,5,6};
int m=sizeof(a)/sizeof(a[0]),n=7;
cout<<"Most repeated number is: "<<getMaxRepeatedNum(a,m,n);
return 0;
}

Sort the numbers using Radix Sort, since the numbers are between some range, O(n) t.c. . Then go for linear search for the required answer.

Cool solution. We have to be concerned about the overflow though (the value of an element can be incremented by n^2). Nice one anyways.

There are not enough info in the question, like can the array hold negative numbers and can we modify the array? If we can modify the array, should we reconstruct it at the end? I assume the answer to these questions is yes yes no.

The solution resembles applying a permutation to an array with minor differences. Since there are no negative numbers in the array, we can use negative numbers to mark cells as visited. Lets call the array A. The algorithm would be:

0. ind := 0
1. starting from ind, find the leftmost index i such that A[i] >= 0. ind := i (terminate if ind >= A.length)
2. a := A[i]
3. A[i] := -infinity (-infinity means we haven't seen i in the array so far)
4. while A[a] >= 0
5. temp := A[a]; A[a] = -1; a :=temp
6. /*here A[a] should be negative*/
7. if A[a] = -infinity then A[a] = -1 else A[a] := A[a] -1
8. go to step 1

At the end just scan through the array and find the minimum value in the array that is not - infinity.

int majority(int *a, int n)
{
  int i, count;
  
  if(n == 0)
    return -1;
  
  if(n == 1)
    return a[0];
  
  for(i = 0, count = 0; i < n; i += 2)
    if(a[i] == a[i+1])
      a[count++] = a[i];
      
  if(n%2 && a[0] == a[n-1])
    a[count++] = a[0];
    
  return majority(a, count);
}

Well, since we know the range of the inputs, we could bucket sort the array in O(n) and scan the resulted list in O(n).

/* 1. Sort the array using Quick sort. O(nlogn) */
/* 2. scan the array using 2 pointers to complete in O(n) */

checkfreq(int a[], int n)
{
	int ffreq =0,freq =1, num = -1, *fptr =a, *sptr=a+1;
	for(int i=1; i< n; i++,sptr++)
	{
		if(*fptr == *sptr)
		{
			++freq;
			
		}else
		{
			if(freq > ffreq)
			{
				freq = ffreq;
				num = *fptr;
			}
			fptr = sptr;
			freq = 1;
		}
	}

	printf(" Max repeating Number : %d with frequency : %d \n", num, ffreq);
}

public class MaxRepeating {
	int[] mIntArray;
	int mMax;
	public MaxRepeating(int[] readIntArray) {
		mIntArray = readIntArray;
		mMax = readIntArray.length;
	}

	public int getMaxRepeatingNumberIndex() {
		for(int i=0; i<mMax;i++){
			int indexToIncrement = mIntArray[i] % mMax;
			mIntArray[indexToIncrement] += mMax;
		}
		int iMaxNumberOfIncrementAtIndex = 0;
		int indexIncrementedMost = -1;
		for(int i=0; i<mMax; i++){
			int iNumberofIncrement = mIntArray[i]/mMax;
			System.out.println("iNumberofIncrement: " + iNumberofIncrement);
			mIntArray[i] =  mIntArray[i]%mMax;
			if( iMaxNumberOfIncrementAtIndex < iNumberofIncrement){
				iMaxNumberOfIncrementAtIndex = iNumberofIncrement;
				indexIncrementedMost = i;
			}
		}
		
		return mIntArray[indexIncrementedMost];
	}

}

Why don't we sort the array and use the HashMap which contains only one value.

Example: 1,3,2,4,2,6,7,4,5,4
After Sorting: 1,2,2,3,4,4,4,5,6,7

Now, iterate over this array, maintain a count variable for each repeated number. For example: for number 2, count: 2. For 4, we get count 3, since this is greater than getCount(2), we simply delete that number from the hashmap and insert this new value.

Since there is no time limitation as such ... why not just perform a heap sort and keep counting the top of maxHeap ... O(1) space would be used by two variables ... one which keeps the previous max and the other one that keeps the current max.

In this case, you also get the O(nlog(n)) time complexity

public static int findMostRepeatingNumber(int[] arr){
		int k = arr.length;
		for(int num : arr){
			arr[num%k] +=k;
		}
		int max = 0;
		
		for(int i =0; i<k; i++){
			if(arr[i]>arr[max]){
				max = i;
			}
		}
		return max;
	}

public int maxRepeatingNo(int[]arr )
  { 
    int[] noLookup = new int[Integer.Max_Value];
    int maxno = 0;
   int maxTime =0;
   for(int i =0 ;i<arr.length;i++)
   {
       int a =arr[i];
         noLookup[a]++;
      if(noLookup[a] > maxTime)
        {
          maxTime = noLookup[a];
          maxno  = a;
         }
} 
}

Time Complexity O(n)
SpaceComplexityO(1)