Elements appear more than n/k times in array

In the given array of size n, find the elements which appear more than n/k times. Where k is the input value

Example

a) Input array: [1, 3, 4, 7, 4, 7, 5], k = 6
    Output: [4, 7]
    Size of array (n) = 7, n/k = 1
    Therefore, we need to find elements which are coming more than 1 time.
    Therefore, output: [4, 7].

b) Input array: [1, 1, 1, 2, 2, 3, 3, 4, 4, 5], k = 5
    Output: [1]
    Size of array (n) =10, n/k = 2
    Therefore, we need to find elements which are coming more than 2 times.
    Therefore, output: [1].

Algorithm

Time complexity: O(nk)

a. Create a structure (struct) which stores the value of the element and its count in the given array

b. Create a temporary array of size k – 1 to store these structs.

c. Traverse through the input array and update temp[] for every element.

    1) If it is new element add this element and initialize count equal to 1.
    2) If it is existing an element then update count by incrementing by 1.

d. If temp[] array is full and we see a new element then,

   1)    We decrease count of every element by 1 in temp[].
   2)    Ignore the current element.

e. Iterate through the final temp[] and check for every element if count more than n/k.

Algorithm working

C++ Program

#include <iostream>
#include <bits/stdc++.h>

using namespace std;
 
// A structure to store an element and its current count
struct Element
{
    int value;  // Element
    int count;  // Count
};
 
//Function to print elements whose occurences is:
//Greater than n/k
void CountGreaterThan(int array[], int n, int k)
{
    //k must be greater than 1
    if (k <= 1)
    {
       return;
    }
    //Temporary array is temp and size is k-1
    //Initialize all elemets count equal to 0
    struct Element temp[k-1];
    for (int i=0; i<k-1; i++)
    {
        temp[i].count = 0;
    }
    //If element already present then increment count
    //If not present and position available then:
    //add element with count equal to 1
    //If there is new element and no available space then:
    //decrese count of all elements by 1 
    for (int i = 0; i < n; i++)
    {
        int j;
        for (j=0; j<k-1; j++)
        {
            if (temp[j].value == array[i])
            {
                 temp[j].count = temp[j].count + 1;
                 break;
            }
        }
        //new element comes
        //position available
        if (j == k-1)
        {
            int p;
            for (p=0; p<k-1; p++)
            {
                if (temp[p].count == 0)
                {
                    temp[p].value = array[i];
                    temp[p].count = 1;
                    break;
                }
            }
            //new element comes
            //no available space to add element
            if (p == k-1)
                for (p=0; p<k; p++)
                {
                    temp[p].count = temp[p].count + 1;
                }
        }
    }
    //In final temp[]
    //check if elements actual count is greater than n/k
    //print if count grater than n/k
    cout<<"Final Output:"<<endl;
    for (int i=0; i<k-1; i++)
    { 
        int correct_count = 0;
        for (int j=0; j<n; j++)
        {
            if (array[j] == temp[i].value)
            {
                correct_count++;
            }
        }
        if (correct_count > n/k)
        {
           cout << "Element: " << temp[i].value<< " with count: " << correct_count << endl;
        }
    }
}
 
/* Driver program to test above function */
int main()
{
    int input_array[] = {1, 1, 1, 2, 2, 2, 2, 4, 4, 5};
    int size = sizeof(input_array)/sizeof(int);
    int k = 5;
    CountGreaterThan(input_array,size,k);
    return 0;
}
Try It


Next > < Prev
Scroll to Top