Google Interview Question
Software Engineer / DevelopersCountry: Israel
Interview Type: In-Person
this is actually the majority voting algorithm. it usually works only if an element appears more than n/2 times. In this case it works for the other ones as well because the array is sorted. In O(n) it is a little bit or over-complication. You could just go through the array and compare it to the previous element.
Its not majority voting algorithm. In Moore's algo you decrease the counter if the currently checked element is different then the candidate till the counter is equal 0.
So the part:
else
{
element=a[i];
count=1;
}
should be change as follows for Moore's algo:
else
{
element=a[i];
count--;
}
In arunkumar267's solution he simply starts counting from the beginning when he finds new value and its perfectly fine.
This algorithm can be optimized (which was interviewer's second part of the question) by performing the following check as the first step in the while loop:
if(maxCount >= (numArr.length - i))
return maxCount;
For 1 1 2 3 4 5
After each element scan :
a. scan 1. count = 2, maximum element = 1
b. scan 1. count = 3 maximum element = 1
c. scan 2. count = 1, maximum element = 1
d. scan 3. count = 0, maximum element = 3
e. scan 5, count = 0, maximum element = 4..
The problem statement says the array is already sorted, so you don't need to bother with all this decrementing counter stuff. Just count instances of last letter, if the counter exceeds max, update max and max letter. O(n)
Below is the java code solution
The first method time complexity is: Θ(n)
The second method average time complexity is: Θ(logn)
:
/**
*
* @author Alex (xiaofan)
*
*/
public class RepetitionsNumber {
/**
* @param args
*/
public static void main(String[] args) {
int[] a = { 1, 2, 2, 3, 3, 3, 4 };
RepetitionsNumber repetitionsNumber =new RepetitionsNumber();
int maxRepNumber=repetitionsNumber
.getBiggestRepetitionsNumber(a);
System.out.println(maxRepNumber);
maxRepNumber = repetitionsNumber
.getBiggestRepetitionsNumberMoreEfficient(a);
System.out.println(maxRepNumber);
}
/**
* Time Complexity Θ(n)
*
* @param a
* @return
*/
public int getBiggestRepetitionsNumber(int[] a) {
int maxRepNumber = 1;
int currentRepNumber = 1;
for (int i = a.length - 1; i > 0; i--) {
int j = i - 1;
if (a[i] == a[j]) {
currentRepNumber++;
} else {
maxRepNumber = maxRepNumber > currentRepNumber
? maxRepNumber: currentRepNumber;
currentRepNumber = 1;
}
}
return maxRepNumber;
}
/**
* Improve one with devide and conquer .
*
* Average Time Complexity Θ(logn) Worst Case Θ(n)
*
* @param a
* @return
*/
public int getBiggestRepetitionsNumberMoreEfficient(int[] a) {
return binaryRepNumber(0, a.length - 1, a);
}
private int binaryRepNumber(int startIndex, int endIndex,int[] a) {
if (startIndex == endIndex) {
return 1;
}
int midIndex = (startIndex + endIndex) / 2;
int midRepNumber = 1;
int leftMidInex = startIndex;
int rightMidIndex = endIndex;
for (int i = midIndex; i > startIndex; i--) {
int j = i - 1;
if (a[i] == a[j]) {
midRepNumber++;
} else {
leftMidInex = j;
break;
}
}
for (int i = midIndex; i < endIndex; i++) {
int j = i + 1;
if (a[i] == a[j]) {
midRepNumber++;
} else {
rightMidIndex = j;
break;
}
}
int leftRepNumber=binaryRepNumber(startIndex,leftMidInex, a);
int rightRepNumber=binaryRepNumber(rightMidIndex,endIndex, a);
int maxRepunumber = leftRepNumber > rightRepNumber
? leftRepNumber: rightRepNumber;
maxRepunumber = maxRepunumber > midRepNumber
? maxRepunumber: midRepNumber;
return maxRepunumber;
}
}
binaryRepNumber - That's more or less what the interviewer was looking for. He noted that you could further refine the solution by using binary search instead of the for loops.
He also noted that the complexity is not O(log n), this is what I thought as well. The complexity is apparently O (n / k ), where k is the length of the longest sequence.
O(log n) is much faster than O(n/k) if the array length is bigger and k is small.
For example: n=1000, k=10 , O(logn)=10 , but O(n/k)=100.
For the length of n=1000, only the K bigger than 100, O(n/k) better than O(logn).
So no one can make sure O(n/k) is faster than O(log n) .
can you guys please help me in understanding how this solution is O(log n)? As far as I see it is still O(n) because eventhough you are splitting the array in the mid, you are still making the comparisons in both the sub arrays.
in binary search, once the array is split, we know if the element lies in one of the sub arrays easily (based on if the element is bigger than or smaller than the mid element)
I think current implementation of binaryRepNumber has O(n) time complexity. In order to reduce it to O(n / k) it is needed to maintain the biggest length of the longest repetition. If length is greater or equal to the length of current interval then do nothing in the current recursion call.
This approach allows to reduce comparisons on leaves of recursion tree.
I think it would be O(n/k) only if the number with occurence k is in the middle. Otherwise, in the worst case you could have all elements distinct and have the largest one with occurence k and it would still be O(n). Can someone give an idea why it would be O(n/k)?
Your first method will not work for this sequence: (imho)
0 1 3 4 1 1 3 4 2
It will return a 2. Whereas the ans is 3 (there are 3 1s in the array)
My solution is O(n^2). which is compare element with every other element.
But that doesn't use the fact that array is sorted
i think it's O(n) for the second method. you have to go to the left and right subarray anyways.
The 'divide and conquer' solution is absolutely NOT O(logn). It still requires checking every element in the array.
To improve on the linear run time, I believe you need to do this optimization: after checking the number of repititions for the middle number, you check if you can eliminate the left or right side (by virtue of their total lengths being less than the number of repitions in the middle). In the case where you're can't eliminate left or right, do either left or right first, whichever is larger (you can choose either if they're the same length). Then you check if you can eliminate the other side from contention before doing the other side.
A few examples:
1 1 2 2 2 2 3 3 4 => here you would counts the 2's. Then instead of recursively checking the number of repetitions one the left hand and right hand side, you can determine that neither can be greater than 4 (because length of left hand side = 2 and length or right hand side = 2).
11111234567 => here you count the one 2 in the middle. Then, arbitrarily, you choose to do the left hand side next. You see it has 5 reps. You can't beat that on the right hand side (it has 5 numbers total), so assuming you can return either number if multiple numbers have the same max #of repitions, you are done.
One more improvement to binary search method above can be to check on the top of the method
if (arr[startIndex] == arr[endIndex]) {
return endIndex - startIndex + 1;
}
This is especially helpful for arrays like 13,13,13,13,13,52,53,53,53,53,53
Nice binary search approach by the way.
This solution is based on the idea of skipping forward by a length equal to the most number of repeats seen so far.
public class MostRepeatingInSortedArray {
public int mostRepeating(int a[]) {
// the index of current element
int current = 0;
int most_repeated = a[0];
int max_repeats = 1;
// just to see how many times the basic operation is done
int complexity = 0;
/* always increment by the max repeats seen so far */
while (current + max_repeats < a.length) {
/* same element again */
if (a[current + max_repeats] == a[current]) {
complexity++;
current += max_repeats;
max_repeats += max_repeats;
most_repeated = a[current];
while (a[current] == a[current + 1]) {
complexity++;
current += 1;
max_repeats++;
}
complexity++;
current++;
} else {
/* different element dound */
complexity++;
/* move the current index */
current += max_repeats;
/* backtrack */
int rep = 1;
while (a[current] == a[current - rep]) {
complexity++;
rep++;
}
complexity++;
/* check elements ahead of you */
int rep2 = 1;
while (a[current] == a[current + rep2]) {
complexity++;
rep2++;
if (current + rep2 == a.length) {
break;
}
}
complexity++;
int total_rep = rep + rep2 - 1;
if (total_rep > max_repeats) {
max_repeats = total_rep;
most_repeated = a[current];
}
current += rep2;
}
}
System.out.println("complexity: " + complexity);
System.out.println("elements: " + a.length);
return most_repeated;
}
public static void main(String[] args) {
MostRepeatingInSortedArray test = new MostRepeatingInSortedArray();
int[] input = new int[] { 1, 1, 1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 6, 6, 6, 6, 7, 8, 9, 9, 9, 9, 9, 10, 11, 12, 12,
12, 13, 13, 13, 13, 13, 13, 13, 22, 23, 24, 32, 33, 35, 36, 55,
55, 55, 55, 55, 56, 56, 57, 58, 59, 59, 59, 60, 65, 65, 65, 65,
65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 66, 66,
66, 67, 67, 68, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70,
70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70,
70, 70, 71, 72, 72, 72, 72, 72, 72, 72, 72, 72, 80, 80, 85, 86 };
int out = test.mostRepeating(input);
System.out.println("most repeated: " + out);
}
}
In Ruby,
Using binary search to find the last positions of each kind of elements, and calculate count.
Using a heap to store all kinds of element and find the max.
Complexity: O(klogn), k is the number of kinds of elements.
In the example, [1,1,2,2,2,2,3,3,3], k will be 3
I'm using array in Ruby to mimic heap.
# [1,1,2,2,2,2,3,3,3]
# heap = [{:num=>2, :count=>4}, {:num=>3, :count=>3}, {:num=>1, :count=>2}]
def find_majority( a )
i = 0
heap = []
while i < a.size
last_i = i
i = bsearch(a, i, a.size-1)
heap << { num: a[i], count: (i-last_i+1).to_i }
heap.sort!{|x,y| y[:count] <=> x[:count] }
i += 1
end
heap.first
end
# [1,1,2,2,2,2,3,3,3]
# when i=0, j=9, it will find 1's last pos, which is a[1]
# when i=2, j=9, it will find 2's last pos, which is a[5]
def bsearch(a, i, j)
return i if i==j
mid = ((i+j)/2).to_i
return mid if a[i]==a[mid] && a[mid] != a[mid+1]
return a[mid] > a[i] ? bsearch(a, i, mid-1) : bsearch(a,mid+1,j)
end
public class Biggest {
public static void main(String args[])
{
int [] a ={1,2,2,3,3,3,3,5,6,6,6,6,6,6,6,7,8,8,8};
int prevnum =a[0];
int count =0;
int maxrepvalue =a[0];
int maxrepcount =0;
for (int i =0;i<a.length-2;i++)
{
prevnum = a[i];
if(prevnum ==a[i+1])
count ++;
else
{
if(count >maxrepcount)
{
maxrepvalue=prevnum;
maxrepcount =count;
}
count=0;
}
}
System.out.println(maxrepvalue +">>" +(maxrepcount+1));
}
}
Just start to count when coming across a different number, the code is easy:
int findRepeatMost(int arr[], int n, int& mostItem)
{
int mostTimes = 0, i, j;
for(i = 0; i < n; i = j){
for(j = i+1; j < n; ++j){
if(arr[j] != arr[i]) break;
}
if(mostTimes < j-i){
mostItem = arr[i];
mostTimes = j-i;
}
}
return mostTimes;
}
Refer to skip list, always try to skip K numbers to avoid unnecessary scan, if encounter a different number, then backward........
great idea!.. i am thinking of few modifications to your approach
1. have a max_repeats initialize to 1
2. keep going till you see different element a2 (incrementing max_repeats)
2. when you see an element different than the current one (a2), skip by max_repeats
3. a. If the number at new location is same as a2, a2 is our new candidate, keep going sequentially
3. b. If the number at new location is different than a2, (is a3) then using 2 pointers scan backwards and forward for a3s
3. b.i if this gets more a3s then make a3 new candidate
4. repeat with new max_repeats as your skip factor
void main(){
int i,j;
int arr[] = {1,2,2,2,4,4,4,48,48,48,48,48,48,48,48};
int length = 14;
int index,count=1,findex,fcount=-1;
for(i=0;i<length-1;){
count = 1;
while(arr[i]==arr[i+1]){
count++;
index=i;
i++;
}
if(arr[i]!=arr[i+1])
i++;
if(fcount<count){
fcount = count;
findex = index;
}
}
printf("\nLargest Frequency number :: %d",arr[findex]);
printf("\nFrequency :: %d",fcount);
}
#include <stdio.h>
int main()
{
int a[] = {1,1,1,1,1,1,1, 2, 2, 2, 3 ,4, 5, 5 , 5 ,5 ,5 };
int n = sizeof(a)/sizeof(a[0]);
int num, max_repeat = 1;
int prev = a[0];
int rep = 1;
int i;
num = a[0];
for (i=0; i < n; i++)
{
if (a[i] == prev)
{
rep++;
}
else
{
if (rep > max_repeat)
{
num = prev;
max_repeat = rep;
}
rep = 1;
}
prev = a[i];
}
if (rep > max_repeat)
{
num = prev;
max_repeat = rep;
}
printf ("Number with max repeatations = %d \n", num );
}
#include<iostream>
using namespace std;
int evalMaxRepeatElem(int *array, int num_Elem){
int maxcount = 1;
int i = 0, count = 0;
int repeatElem = array[0];
while( i<num_Elem ){
while(array[i] == array[++i])
count++;
if(count > maxcount)
repeatElem = array[i-1];
}
return repeatElem;
}
int main(){
int array[] = {1,1,1,1,2,3,3,3,5,5,5,5,5,5,7,7,7,7,7,7,7,7,7,7,7,8,9,9};
int maxRepeatElement;
maxRepeatElement = evalMaxRepeatElem(array, sizeof(array)/sizeof(array[0]));
cout<<maxRepeatElement<<"\n";
}
Here's a short Implementation in Python
count = 0
def MaximumRepeatingInteger(arrayofnumber):
global count
dict_of_counts = {}
for integer in arrayofnumber:
if dict_of_counts.has_key(str(integer)):
count +=1
dict_of_counts[str(integer)]=count
else:
count = 1
dict_of_counts[str(integer)]=count
return max(dict_of_counts.values())
number = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 5]
print MaximumRepeatingInteger(number) : 14
number=[1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 5]
print MaximumRepeatingInteger(number) : 21
In Go
package main
import "fmt"
func main() {
b:= []int{1,1,2,2,2,3,3,4,5,7,15,15,15,15,15,17}
max_count := 1
count := 1
max_value := b[0]
for i:=1; i < len(b) ; i++ {
// We increment the count if the same value
if b[i-1] == b[i] {
count = count + 1
}
if b[i] != b[i-1] {
count = 1
}
if count > max_count {
max_count = count
max_value = b[i]
}
}
fmt.Println("Total value:", max_value, "appears",max_count,"times")
}
For sorted:
int max_value = A[0], max_count = 1;
int value = A[0], count = 1;
for(int i=1; i<N; ++i)
if(A[i] == A[i-1])
{
++count ;
if(max_count <count )
{
max_value = value ;
max_count = count ;
}
}
else
{
value = A[i];
count = 1;
}
Time: O(N)
Space: O(1)
For unsorted:
Data structure: treap (tree+heap)
http://en.wikipedia.org/wiki/Treap
http://e-maxx.ru/algo/treap
sorted tree by value + max-head by count
root will be the answer
Time: O(N Log(N))
Space: O(N)
O(n) complexity with no additional space
/*
Given a sorted array of integers, write a function that will return the number with the biggest number of repetitions.
(Asked to refine the solution to be more efficient)
*/
#include <iostream>
#include <vector>
static int max_rep(const std::vector<int>& vec) {
int big_cnt = 0;
int saved_int;
int cnt;
saved_int = vec[0];
cnt = 1;
big_cnt = 1;
for(int i = 1; i < vec.size(); i++) {
if(saved_int == vec[i]) {
++cnt;
continue;
}
// Different
if(cnt > big_cnt) {
big_cnt = cnt;
}
saved_int = vec[i];
cnt = 1;
}
if(cnt > big_cnt)
big_cnt = cnt;
return big_cnt;
}
int main() {
std::vector<int> vec{1, 1, 1, 3, 3, 3, 3, 3, 5, 5, 5, 5, 5, 5, 5};
std::cout << max_rep(vec) << std::endl;
return 0;
}
public static void LargeRepetations(int[] arr)
{
int len = arr.Length;
int mostFreq = arr[0];
int largeFre=1;
int currentFre = 1;
for (int i = 1; i < len; i++)
{
if (arr[i-1]!=arr[i])
{
currentFre = 1;
}
else
{
currentFre++;
}
if (largeFre < currentFre)
{
largeFre = currentFre;
mostFreq = arr[i];
}
}
#include<stdio.h>
#include<conio.h>
void main(){
int a[] = {2,7,9,7,5,7,0,9,4,3,5,7};
int i,j,max=0,number,k;
for(i=0;i<12;i++){
number=1;
for(j=i+1;j<12;j++){
if(a[j]==a[i])
number++;
}
if(number>max){
k=a[i];
max=number;
}
}
printf("MAximum occurence of a number is: %d and the number is %d", max,k);
getch();
}
public static void main(String[] args) {
int[] intArray= { 1, 1, 1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 6, 6, 6, 6, 7, 8, 9, 9, 9, 9, 9, 10, 11, 12, 12,
12, 13, 13, 13, 13, 13, 13, 13, 22, 23, 24, 32, 33, 35, 36, 55,
55, 55, 55, 55, 56, 56, 57, 58, 59, 59, 59, 60, 65, 65, 65, 65,
65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 66, 66,
66, 67, 67, 68, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70,
70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70,
70, 70, 71, 72, 72, 72, 72, 72, 72, 72, 72, 72, 80, 80, 85, 86 };
int count=0;
int pricount=0;
int currentNo=intArray[0];
int maxInt=0;
int i=0;
for(int no:intArray){
if(no==currentNo){
count++;
}else{
if((count>pricount)){
pricount=count;
maxInt=currentNo;
}
count=1;
currentNo=no;
}
i++;
}
if((i==intArray.length)){
if(count>pricount){
pricount=count;
maxInt=currentNo;
}
System.out.println("Maxi int :"+maxInt +" and count : " +pricount);
}
// TODO Auto-generated method stub
}
What should be the complexity for the following, as this seems like the easiest approach to me:
HashMap<Integer, Integer> test = new HashMap<>();
Integer[] array = {1,2,3,1,1,3,2,2,2,2};
int maxKey =0;
int maxValue=0;
int newCounter =0;
for (Integer check: array)
{
if (!test.containsKey(check))
{
test.put(check, 1);
System.out.println("FIRST key:"+check+" counter:"+1);
}
else
{
newCounter=test.get(check)+1;
test.put(check, newCounter);
if (newCounter>maxValue)
{
maxValue=newCounter;
maxKey=check;
}
System.out.println("key:"+check+" counter:"+test.get(check));
}
}
int maxRepetitionCount =0;
int maxRepetitiveElement =0;
int tmp =0;
for(int i =0; i< a.length-1;i++) {
if(a[i+1] == a[i]) {
tmp++;
}else if( tmp > 0) {
//Repetition sequence ends
if(tmp > maxRepetitionCount) {
maxRepetitionCount = tmp;
maxRepetitiveElement = a[i];
if(maxRepetitiveElement > (a.length-1 -i)) {
//Not enough elements left to overcome this value
tmp =0;
break;
}
}
tmp =0;
}
}
//if max repetiting element is the last element
if(tmp > maxRepetitionCount) {
maxRepetitionCount = tmp;
maxRepetitiveElement = a[a.length -1];
}
System.out.println(maxRepetitiveElement+" "+(++maxRepetitionCount));
This one has also o(n) as worst case (when the largest run is very small, e.g 2). however, it gets much better as runs grow. For example, a run of size 200 in an array of size 1000 would require only ~50 comparisons. A run of size 60 in the same array requires ~150.
static int
bsearch_run_boundary (int *a, int num, int start, int end, int is_begin, int *cmp)
{
int org_end = end, org_start = start;
int mid;
while (start < end) {
(*cmp)++; // count the num of comparisons
mid = start + ((end - start) / 2);
if (a[mid] < num) {
start = mid+1;
} else if (a[mid] > num) {
end = mid-1;
} else if (is_begin) {
if (mid == org_start || a[mid-1] < num) return mid;
end = mid-1;
} else {
if (mid == org_end || a[mid+1] > num) return mid;
start = mid+1;
}
}
return a[start] == num ? start : -1;
}
static void
largest_run (int *a, size_t n, int *maxrun, int *cmp)
{
int mid = n / 2;
int midval = a[mid];
int begin, end, run;
// find the beginning of this run
begin = bsearch_run_boundary(a, midval, 0, mid, 1, cmp);
// find the end of this run
end = bsearch_run_boundary(a, midval, mid, n-1, 0, cmp);
assert(begin >= 0 && end >= 0);
run = end - begin + 1;
printf("-> run (%d) = %d\n", midval, run);
// is it the largest run so far?
if (run > *maxrun) *maxrun = run;
// check the lower range if it has potential for a larger run
if (begin > *maxrun) {
largest_run(a, begin-1, maxrun, cmp);
}
// check the higher range if it has potential for a larger run
if (n - end - 1 > *maxrun) {
largest_run(a + end + 1, n - end - 1, maxrun, cmp);
}
}
public static void main(String[] args) {
int[] testArr = new int[] { 1,1, 9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9
};
int maxFreq = 0;
int currentFreq = 0;
int max = testArr[0];
for (int i = 1; i <= testArr.length - 1; i++) {
currentFreq++;
int prev = testArr[i-1];
int next = testArr[i];
if (prev != next || (i == testArr.length - 1)) {
if (maxFreq <= currentFreq) {
max = testArr[i-1];
maxFreq = currentFreq;
}
currentFreq = 0;
}
}
System.out.println("Max freq " + maxFreq + " Number " + max);
}
i don't think dividing with binary can help as you still need to scan whole array. Here is my take on this. it will skip k where k is max known so far. So its best will be o(n/k) and worst will be O(n)
int findMaxRepead(int[] num)
{
int maxCount = 0;
if (num.GetLength(0) > 0)
{
int i = 1;
int count = 1;
int currNum = num[0];
while (i < num.GetLength(0))
{
if (num[i] == currNum)
{
if (count > maxCount)
{
maxCount = count;
}
i = i + maxCount;
count += maxCount;
}
else
{
count = 1;
currNum = num[i];
int j = i - 1;
while (j >= 0 && currNum == num[j])
{
j--;
count++;
}
}
}
}
return maxCount;
}
without using binary search, you're not taking any advantage of the fact that the array is _sorted_ .
not accurate, the reason i can skip k is due to the fact that array is sorted otherwise i had to scan all. Problem itself is not divide concur kind of thing its more of a scanner. In scanner kind of problems only optimization you can do is how many do you can skip. Do you have case that shows binary algo will out perform what i posted above. :)
for skipping k elements it's enough to assume that the numbers are grouped in "runs", but you don't need the groups themselves to be in ascending order. For example, the skipping algo works for a case like [ 3, 3, 1, 1, 1, 2, 2]. Think about a case where you have a run which is bigger than n/2 . Therefore, this run has to cross the array's middle point. The binary search starts from the middle, so it finds it right away, while the skipping algo may need n/2 steps. if the run is n/4 long, then binary search finds it at the 2nd round, and so on. The advantage of "random sampling" in oppose to linear scanning is that large runs have a higher probability to be sampled than small runs. Now there are two ways of doing the binary search. The one listed above is similar to DFS (depth first). There's also a BFS approach, where all the level-2 ranges are handled before starting to handle level-3 ranges, etc. The BFS might be better, because if the largest run is located at the array end, then it would be found soon enough to suppress the exploring of smaller ranges.
int most_freq(const int *i, const int size)
{
if(0 == size) return -1;
int count = 1;
int m;
int prev = i[0];
int highest_count = count;
int retVal = i[0];
for(m=1; m<size; ++m)
{
if(i[m] == prev)
{
count++;
if(count > highest_count)
{
highest_count = count;
retVal = i[m];
}
}
else
{
prev = i[m];
count = 1;
if(i[m + highest_count -1 ] == prev)
{
count = highest_count;
m+=highest_count-1;
}
}
}
return retVal;
}
#include<stdio.h>
#include<conio.h>
main()
{
int i , j, a[20], n, count =0, maxrepeat=0,maxrepeatvalue;
printf("entr the size of array ");
scanf("%d", &n);
printf("enter the element");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]==a[j]){
count++;}
else
{
if (count > maxrepeat)
{
maxrepeatvalue=a[i];
maxrepeat=count;
count=0;
}
}
}
}
printf("total count =%d \n maximum repeated number %d\n", maxrepeat+1, maxrepeatvalue);
getch();
}
#include<stdio.h>
#include<conio.h>
main()
{
int i , j, a[20], n, count =0, maxrepeat=0,maxrepeatvalue;
printf("entr the size of array ");
scanf("%d", &n);
printf("enter the element");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]==a[j]){
count++;}
else
{
if (count > maxrepeat)
{
maxrepeatvalue=a[i];
maxrepeat=count;
count=0;
}
}
}
}
printf("total count =%d \n maximum repeated number %d\n", maxrepeat+1, maxrepeatvalue);
getch();
}
#include<stdio.h>
#include<conio.h>
main()
{
int i , j, a[20], n, count =0, maxrepeat=0,maxrepeatvalue;
printf("entr the size of array ");
scanf("%d", &n);
printf("enter the element");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]==a[j]){
count++;}
else
{
if (count > maxrepeat)
{
maxrepeatvalue=a[i];
maxrepeat=count;
count=0;
}
}
}
}
printf("total count =%d \n maximum repeated number %d\n", maxrepeat+1, maxrepeatvalue);
getch();
}
#include<stdio.h>
#include<conio.h>
main()
{
int i , j, a[20], n, count =0, maxrepeat=0,maxrepeatvalue;
printf("entr the size of array ");
scanf("%d", &n);
printf("enter the element");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]==a[j]){
count++;}
else
{
if (count > maxrepeat)
{
maxrepeatvalue=a[i];
maxrepeat=count;
count=0;
}
}
}
}
printf("total count =%d \n maximum repeated number %d\n", maxrepeat+1, maxrepeatvalue);
getch();
}
#include<stdio.h>
#include<conio.h>
main()
{
int i , j, a[20], n, count =0, maxrepeat=0,maxrepeatvalue;
printf("entr the size of array ");
scanf("%d", &n);
printf("enter the element");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]==a[j]){
count++;}
else
{
if (count > maxrepeat)
{
maxrepeatvalue=a[i];
maxrepeat=count;
count=0;
}
}
}
}
printf("total count =%d \n maximum repeated number %d\n", maxrepeat+1, maxrepeatvalue);
getch();
}
#include<stdio.h>
int count(int[],int);
int max = 1;
int tempmax = 1;
int count(int a[],int size){
for(int i=0;i<size;i++)
{
if(a[i]==a[i+1])
max++;
else
{
printf("\n [ %d ]-> %d",a[i],max);
if(max>tempmax)
{
tempmax = max;
max = 0;
}
}
}
if(max>tempmax)
return max;
else
tempmax;
}
int main()
{
int arr[] = {1,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5};
int maxcount = count(arr,(sizeof(arr)/sizeof(int)));
printf("\n highest -> %d",maxcount);
}
package com.tutorial.sorting;
public class GetMaxNumberRepeatedTest {
public static void main(String[] args) {
GetMaxNumberRepeatedTest gmrt = new GetMaxNumberRepeatedTest();
int[] testList1 = new int[]{1};
int[] testList2 = new int[]{1,2,3,4};
int[] testList3 = new int[]{1,2,2,3,4,4,5,5,5,6,6,6,7};
int[] testList4 = new int[]{1,2,2,3,3,3};
System.out.println("==========================================");
System.out.println("\t Get Number Repeated Most Times \t");
System.out.println("==========================================");
System.out.println("Test Case 1: Expected: -1 Actual: " + gmrt.getMaxNumberRepeated(testList1));
System.out.println("Test Case 2: Expected: -1 Actual: " + gmrt.getMaxNumberRepeated(testList2));
System.out.println("Test Case 3: Expected: 5 Actual: " + gmrt.getMaxNumberRepeated(testList3));
System.out.println("Test Case 4: Expected: 3 Actual: " + gmrt.getMaxNumberRepeated(testList4));
}
public int getMaxNumberRepeated(int[] listSorted) {
// Base Case
if(listSorted.length < 2) {
return -1;
}
int countMaxRepeated = 0;
int itemMaxRepeated = -1;
int countCurrentRepeated = 0;
int itemCurrentRepeated = -1;
for(int i=1; i < listSorted.length; ++ i) {
if(listSorted[i] == listSorted[i-1]) {
itemCurrentRepeated = listSorted[i];
++ countCurrentRepeated;
}
else {
countCurrentRepeated = 0;
}
if(countCurrentRepeated > countMaxRepeated) {
countMaxRepeated = countCurrentRepeated;
itemMaxRepeated = itemCurrentRepeated;
}
}
return itemMaxRepeated;
}
}
Here is klogn solution using Binary search.
int main(void) {
int a[] = {1,1,1,2,2,2,3,4,4,4,4};
int max = 0;
int size = sizeof(a)/sizeof(a[0]);
int maxRepetitions = numberWithRepetitions(a, 0, size, max);
printf("%d", max);
return 0;
}
int numberWithRepetitions( int[] a, int low, int high, int *maxNo){
if(a.length == 0){
return 0;
}
if( a.length == 1){
*maxNo = a[0];
return 1;
}
int mid = high + low/2;
if( a[low] == a[mid] && a[high] == a[mid]){
*max = a[low];
return high-low ;
}
int range = 0;
int leftHigh = mid;
while( a[mid] == a[leftHigh] ){
range ++;
leftHigh--;
}
int rightLow = mid+1;
while(a[mid] == a[rightLow]){
range++;
rightLow++;
}
*max = a[mid];
return (max(range,
(max(numberWithRepetitions(a, low, leftHigh, &maxNo),
numberWithRepetitions(a, rightLow, right, &maxNo));
}
//correction in last part of the code
int maxleft, maxright;
int maxRepetitions
int leftMaxRepetitions = numberWithRepetitions(a, low, leftHigh, &maxleft) ;
int rightMaxRepetitions = numberWithRepetitions(a, rightLow, right, &maxRight);
if( leftMaxRepetitions > rightMaxRepetitions ){
maxRepetitions = leftMaxRepetitions;
*maxNo = maxLeft;
}else{
maxRepetitions = rightMaxRepetitions;
*maxNo = maxRight;
}
if( range > maxRepetitions){
maxRepetitions = range;
*maxNo = a[mid];
}
return maxRepetitions;
Build a list for representing non-uniform segments using recursion. Each element contains a value and an index. The Space O(n/k), Time O(n/k) where k is the average number of repeats.
public class GetValueWithMaxRepeats {
private static final boolean DEBUG = false;
public static int getNumberWithMaxRepeats(int [] arr) { // input is a sorted array
int n = arr.length;
if( n < 1) throw new IllegalArgumentException("Empty input array");
int curCount = 1, curValue = arr[0];
int maxCount = Integer.MIN_VALUE, maxValue = curValue;
for(int i = 1; i < n; i++){
if(curValue ==arr[i]){
curCount++;
} else {
if(curCount > maxCount) {
maxCount = curCount;
maxValue = curValue;
}
curCount = 1;
curValue = arr[i];
}
}
if(curCount > maxCount) {
maxCount = curCount;
maxValue = curValue;
}
return maxValue;
}
private static class LNode {
LNode next;
int index;
int value;
LNode (int idx, int val) { index = idx; value = val; }
@Override
public String toString() {
return "<"+value+" @ "+ index+">";
}
}
public static int getNumberWithMaxRepeats_eff(int [] arr) { // input is a sorted array
int n = arr.length;
if( n < 1) throw new IllegalArgumentException("Empty input array");
if( n == 1) return arr[0];
LNode start = new LNode(0,arr[0]);
LNode end = new LNode(n-1, arr[n-1]);
start.next = end;
createList(arr, start, end);
if(DEBUG) {
System.out.println("The list is: ");
printList(start);
}
int curCount = 1;
int maxCount = Integer.MIN_VALUE, maxValue = start.value;
LNode prevNode = start;
LNode cur = start.next;
while(cur!=null){
if(cur.value != prevNode.value){
if(curCount > maxCount) {
maxCount = curCount;
maxValue = prevNode.value;
}
curCount = 1;
} else {
curCount+=cur.index - prevNode.index;
}
prevNode = cur;
cur=cur.next;
}
if(curCount > maxCount) {
maxCount = curCount;
maxValue = prevNode.value;
}
return maxValue;
}
private static void printList(LNode start) {
LNode cur = start;
while(cur != null) {
System.out.print(cur+"->");
cur = cur.next;
}
System.out.println("||");
}
private static void createList(int[] arr, LNode start, LNode end) {
if(DEBUG) System.out.println("Start="+ start+", end="+end);
if(start.value == end.value || start.index + 1 == end.index) return;
int midIdx = (start.index + end.index)/2;
LNode mid = new LNode(midIdx, arr[midIdx]);
start.next = mid;
mid.next = end;
createList(arr,start,mid);
createList(arr,mid,end);
}
public static void main(String[] args) {
int [] arr = { 1,1,1,1,1,1,1,1,1,1, 2,2,2,2,2,2,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,6,6,7,8,8,8,8,8,8,8,8 };
System.out.println(getNumberWithMaxRepeats(arr));
System.out.println(getNumberWithMaxRepeats_eff(arr));
}
}
public class MaxRepetations {
public static void main(String[] args) {
int a[]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,3,3,3,3,3,4,4,4,4,4,4,4,5};
maxRep(a);
}
public static void maxRep(int[] a){
int maxcount =1;
int count =1;
for(int i=0;i<a.length;i++){
if(i!=a.length-1){
if(a[i]==a[i+1]){
count++;
}else{
if(count>maxcount){
maxcount = count;
count = 0;
}else{
count =0;
}
}
}
}
System.out.println("Max Count "+maxcount);
}
}
here is an algorithm whose best case is O(logN), worse case is O(N)
public static int findBiggestRepetitions(int[] arr){
int p = 1,c =0;
for(int i = 0; i<arr.length;i++){
while(i+p<arr.length && arr[i] == arr[i+p])
p *=2;
if(p!=1){
if(p>2){
int t = p/4;
p = p-t;
while(t>0){
t = t/2;
if(arr[i] == arr[i+p])
p +=t;
else
p-=t;
}
}
if(p>c)
c=p;
i=i+p-1;
p=1;
}
}
return c;
}
public class Main {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] tab = new int[]{1,1,1,1,3,3,4,4,4,4,8,8,9,9,9,9,9,9,9};
System.out.println(getBiggestRepetition(tab, tab.length));
}
public static int getBiggestRepetition(int[] array, int n)
{
int elm1, elm2, occ1, occ2;
if(n==0) return -99999;
elm1 = array[0];
occ1 = 1;
int i = 1 ;
while((i<n)&&(array[i]==elm1))
{
occ1++;
i++;
}
if(i==n) return elm1;
else
{
elm2 = array[i];
occ2 = 0;
for(; i<n ; i++)
{
if(array[i]==elm2)
occ2++;
else
{
if(occ1<occ2)
{
occ1 = occ2;
elm1 = elm2;
}
elm2 = array[i];
occ2 = 1;
}
}
}
if(occ1<occ2)
return elm2;
return elm1;
}
}
public class App
{
public static void main( String[] args )
{
ArrayList<Integer> randomList = new ArrayList<Integer>();
Map<Integer, Integer> countMap = new HashMap<Integer, Integer>();
for(int j =1; j<=10;j++)
{
randomList.add((int) ((Math.random()*10))+1);
}
int maxCount= 1;
int maxElement=randomList.indexOf(0);
for (Integer num : randomList)
{
int count=0;
if(!countMap.containsKey(num))
{
countMap.put(num, 1);
}
else
{
count = countMap.get(num)+1;
countMap.put(num,count);
}
if(count>= maxCount)
{
maxElement = num;
maxCount = count;
}
}
for ( Integer key : countMap.keySet() ) {
System.out.println( key+" "+ countMap.get(key));
}
/*for (Integer listNumber : randomList) {
System.out.println(listNumber);
}*/
System.out.println(maxElement);
}
}
O(n) time O(1) space, I think this question is so simple, just go forward and keep track of max seen element
int findMostRepeatedNumber(vector<int>& array) {
int max_count=1;
int max_value=array[0];
int count=1;
int pre=array[0];
for(int i=1; i<array.size(); ++i) {
if(array[i]==pre) {
count++;
}else{
count=1;
pre=array[i];
}
if(count>max_count){
max_count=count;
max_value=pre;
}
}
return max_value;
}
Since its said that the array is already sorted,
int findMaxRepeat(int a[], int cnt){
int maxEle = 0;
int maxCount = 0;
int curEle = 0;
int count = 0;
int i;
curEle = a[0];
maxCount = 0;
for(i=0;i<cnt;i++){
if(a[i] == curEle){
count++;
if(maxCount<count){
maxCount = count;
maxEle = a[i];
}
}
else{
curEle = a[i];
count = 1;
}
}
return maxEle;
}
#include<iostream>
using namespace std;
int find(int a[],int n){
for(int i=0;i<n;i++){
a[a[i]]+=n;
}
int res=0;
int maxi=a[0];
for(int i=1;i<n;i++){
if(maxi>a[i]){
maxi=a[i];
res=i;
}
}
return res;
}
int main(){
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
cout<<find(a,n)<<endl;
}
**
* Given a sorted array of integers,
* write a function that will return the number with the biggest number of repetitions.
*/
public class RepeatCounter {
private final Stack<TabKeeper> tabKeepers = new Stack<>();
private int[] numArrs = new int[]{2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 6, 9, 9, 9, 9, 9};
private int numArrsLength = numArrs.length;
private int currentValue = numArrs[0];
private int currentCounter = 0;
public String getMaxOccurrence() {
for (int index = 0; index < numArrsLength; index++) {
if (currentValue == numArrs[index]) {
currentCounter++;
if (index == numArrsLength - 1)
saveCount(index);
} else {
saveCount(index);
}
}
TabKeeper tabKeeper = tabKeepers.pop();
return "The number " + tabKeeper.number + " occurs " + tabKeeper.numberMaxOccurrence + " times";
}
private void saveCount(int index) {
if (tabKeepers.isEmpty()) {
tabKeepers.push(new TabKeeper(currentValue, currentCounter));
moveToNext(index);
} else {
if (tabKeepers.peek().numberMaxOccurrence < currentCounter) {
tabKeepers.pop();
tabKeepers.push(new TabKeeper(currentValue, currentCounter));
}
moveToNext(index);
}
}
private void moveToNext(int index) {
currentValue = numArrs[index];
currentCounter = 0;
currentCounter++;
}
public class TabKeeper {
private int number;
private int numberMaxOccurrence;
public TabKeeper(int number, int numberMaxOccurrence) {
this.number = number;
this.numberMaxOccurrence = numberMaxOccurrence;
}
}
}
A solution with O(n) time complexity and O(1) space complexity.
Logic:1) maintain 4 variables called count and element element,max count,max element.Initialise count to 1 and maximum element to 1st element of array.
2) while traversing if the element is same as maximum count then increment count by one.
3)Else decrement count.If count reaches zero then assign maximum element to the element at which count became zero and reinitialise the variables
- arunkumar267 December 30, 2013