C++ program to print all the Repeated Numbers with Frequency in an Array

In this article we are going to see how to print all the repeating numbers with their frequency in an array with use of STL?
Submitted by Radib Kar, on December 19, 2018

Problem statement: Write a C++ program to print all the repeated numbers with their frequency in an array in minimum time complexity.

Input Example:

    Array length: 10
    Array input: 2 5 3 2 4 5 3 6 7 3
    Output:
    Repeated number	Frequency
    3			3
    5			2
    2			2

Solution

Data structures used:

    Unordered_map <int, int>
  • Key in the map is array value
  • Value of key is frequency

Algorithm:

  1. Declare a map hash to store array elements as keys and to associate their frequencies with them.
  2.     Unordered_map <int, int>hash;
    
  3. For each array element
    Insert it as key & increase frequencies.
    For same key it will only increase frequencies.
  4. For i=0: n-1
    	hash[array [i]]++;
    End For
    
  5. Now to print the repeated character we need to print the keys (array elements) having value (frequencies) more than 1.
    Set an iterator to hash.begin().
    iterator->first is the key (array element) & iterator->second is the value( frequency of corresponding array value)
  6. IF
        Iterator->second > 1
        Print iterator->first & iterator->second
    END IF
    

Explanation with example:

For this array: 2 5 3 2 4 5 3 6 7 3

The code:

for(int i=0;i<n;i++){//creating the map
    hash[a[i]]++;//for same key increase frequency
}

Actually does the following

    At i=0
    array[i]=2
    Insert 2 & increase frequency

    Hash:
    Key(element)	Value(frequency)
    2	            1

    At i=1
    array[i]=5
    Insert 5 & increase frequency

    Hash:
    Key(element)	Value(frequency)
    2	            1
    5	            1


    At i=2
    array[i]=3
    Insert 3 & increase frequency

    Hash:
    Key(element)	Value(frequency)
    2	            1
    5	            1
    3	            1

    At i=3
    array[i]=2
    Insert 2 increase frequency
    '2' is already there, thus frequency increase.

    Hash:
    Key(element)	Value(frequency)
    2	            2
    5	            1
    3	            1

    At i=4
    array[i]=4
    Insert 4 &increase frequency

    Hash:
    Key(element)	Value(frequency)
    2	            2
    5	            1
    3	            1
    4	            1

    At i=5
    array[i]=5
    '5' is already there, thus frequency increase.

    Hash:
    Key(element)	Value(frequency)
    2	            2
    5	            2
    3	            1
    4	            1

    At i=6
    array[i]=3
    '3' is already there, thus frequency increase.

    Hash:
    Key(element)	Value(frequency)
    2	            2
    5	            2
    3	            2
    4	            1

    At i=7
    array[i]=6
    Insert 6, increase frequency.

    Hash:
    Key(element)	Value(frequency)
    2	            2
    5	            2
    3	            2
    4	            1
    6	            1

    At i=8
    array[i]=7
    Insert 7, increase frequency.

    Hash:
    Key(element)	Value(frequency)
    2	            2
    5	            2
    3	            2
    4	            1
    6	            1
    7	            1

    At i=9
    array[i]=3
    '3' is already there, thus frequency increase.

    Hash:
    Key(element)	Value(frequency)
    2	            2
    5	            2
    3	            3
    4	            1
    6	            1
    7	            1

C++ implementation to print all the Repeated Numbers with Frequency in an Array

#include <bits/stdc++.h>

using namespace std;


void findRepeat(int* a, int n){
    //Declare the map
    unordered_map<int,int> hash;
    
    for(int i=0;i<n;i++){//creating the map
        hash[a[i]]++;//for same key increase frequency
    }
    
    cout<<"repeated number      frequency\n";
    //iterator->first == key(element value)
    //iterator->second == value(frequency)
    
    for(auto it=hash.begin();it!=hash.end();it++)
    if(it->second>1)//frequency>1 means repeating element
    printf("%d\t\t\t%d\n",it->first,it->second);
    
}

int main()
{
    int n;
    cout<<"enter array length\n";
    cin>>n;
    int* a=(int*)(malloc(sizeof(int)*n));
    
    cout<<"input array elements...\n";
    
    for(int i=0;i<n;i++)
    scanf("%d",&a[i]);
    
    //function to print repeating elements with their frequencies
    findRepeat(a,n);

    return 0;
}

Output

enter array length
10
input array elements...
2 5 3 2 4 5 3 6 7 3
repeated number      frequency
3               	3
2               	2
5               	2



Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.