Objective: Given an array of size of N and number k. Find all elements in an Array which appears more than N/K times.
Input: Array [] and number k.
Example:
int[] arrA = { 2, 2, 4, 4, 3, 5, 3, 4, 4, 6, 4, 3, 3, 8 }; K = 4 N/k = 14/4 = 3 Output will be [3,4] they appear 5, 4 times respectively.
Approach:
Naive Approach: Take two for loops , check every element with all other elements, Time Complexity – O(n2) time.
Better Approach: Tetris Game technique- O(Nk)
- We will create a class structure which will store an element and its count.
class Elements{ intelement; intcount; public Elements(int element, int count){ this.element = element; this.count =count; } }
- Create array etms[] contains k-1 objects of class Elements with element =0 and count = 0.
- So idea is, navigate all the elements of given array.
- Check if element exist in etms[] if not, insert it with the count 1 and if exist then increase its count.
- Also check if etms[] gets full when inserting an element, if it is not, follow the previous step. If it is full then reduce the count of every existing element in the etms[]. (Just think of a Tetris game, when row gets full, it gets deleted and size of the Tetris reduced by 1) see the picture below.
- Once all the elements of array gets over, check every element of etms[] with array and print those elements which has N/K times.
Complete Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//Objective is to find the element in an array | |
///which occurs more than n/k times | |
public class NbyKTimes { | |
public void findElement(int[] arrA, int k) { | |
Elements[] emts = new Elements[k – 1]; | |
for (int j = 0; j < emts.length; j++) { | |
emts[j] = new Elements(0, 0); | |
} | |
for (int i = 0; i < arrA.length; i++) { | |
int index = found(emts, arrA[i]); | |
if (index >= 0) { | |
// means element found in Elements array | |
// just increase its count | |
emts[index].count++; | |
} else { | |
addtoArray(emts, arrA[i]); | |
} | |
}// | |
// now check if any of the elements in the Elements array appears | |
// more than n/k times | |
for (int i = 0; i < emts.length; i++) { | |
int cnt = 0; | |
for (int j = 0; j < arrA.length; j++) { | |
if (arrA[j] == emts[i].element) { | |
cnt++; | |
} | |
} | |
if (cnt > (arrA.length / k)) { | |
System.out.println(emts[i].element + " appears more than n/" | |
+ k + " times, Actual count is " + cnt); | |
} | |
} | |
} | |
public void addtoArray(Elements[] emts, int x) { | |
// check is array is full or not | |
for (int j = 0; j < emts.length; j++) { | |
if (emts[j].count == 0) {// find the empty place and add it | |
emts[j].element = x; | |
return; | |
} | |
} | |
// if we have reached here means array is full | |
// reduce the counter of every element | |
for (int j = 0; j < emts.length; j++) { | |
emts[j].count—; | |
} | |
} | |
// This found function will check whether element already exist or not | |
// if yes then return its index else return -1 | |
public int found(Elements[] emts, int x) { | |
for (int j = 0; j < emts.length; j++) { | |
if (emts[j].element == x) { | |
return j; | |
} | |
} | |
return –1; | |
} | |
public static void main(String args[]) { | |
int[] arrA = { 2, 2, 4, 4, 3, 5, 3, 4, 4, 6, 4, 3, 3, 8 }; | |
NbyKTimes n = new NbyKTimes(); | |
n.findElement(arrA, 4); | |
} | |
} | |
class Elements { | |
int element; | |
int count; | |
public Elements(int element, int count) { | |
this.element = element; | |
this.count = count; | |
} | |
} |
Output:
4 appears more than n/4 times, Actual count is 5 3 appears more than n/4 times, Actual count is 4