Home » Interview Questions » Array Interview Questions » Elements appear more than n/k times in array

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;
}

READ  Sort Colors

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions