Check if frequency of each digit in a number is equal to its value
Given a number N the task is to check whether the frequency of each digit in a number is equal to its value or not
Examples:
Input: N = 3331
Output: Yes
Explanation: It is a valid number since frequency of 3 is 3, and frequency of 1 is 1
Input: N = 121
Output: No
Explanation: It is not a valid number since frequency of 1 is 2, and frequency of 2 is 1
Approach: The task can be solved by storing the frequencies of a digit in a hashmap and then iterating the hashmap to check whether the frequency of the digit is equal to its value or not.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if the number // is valid or not void check( int N) { // Stores the frequencies // of digits unordered_map< char , int > occ; while (N > 0) { // Extracting the digits int r = N % 10; // Incrementing the frequency occ[r]++; N /= 10; } // Iterating the hashmap for ( auto i : occ) { // Check if frequency of digit // is equal to its value or not if (i.first != i.second) { cout << "No\n" ; return ; } } cout << "Yes\n" ; } int main() { int N = 3331; check(N); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.HashMap; import java.util.Map; class GFG { // Function to check if the number // is valid or not public static void check(Integer N) { // Stores the frequencies // of digits HashMap<Integer, Integer> occ = new HashMap<>(); while (N > 0 ) { // Extracting the digits Integer r = N % 10 ; if (occ.containsKey(r)) { // If char is present in charCountMap, // incrementing it's count by 1 occ.put(r, occ.get(r) + 1 ); } else { // If char is not present in charCountMap, // putting this char to charCountMap with 1 // as it's value occ.put(r, 1 ); } N = N / 10 ; } for (Map.Entry<Integer, Integer> e : occ.entrySet()) { if (e.getKey() != e.getValue()) { System.out.print( "NO" ); return ; } } System.out.print( "Yes" ); } // Driver code public static void main(String[] args) { Integer N = 3331 ; check(N); } } // This code is contributed by Potta Lokesh |
Python3
# Python program for the above approach # Function to check if the number # is valid or not def check(N): # Stores the frequencies # of digits occ = dict (); while (N > 0 ): # Extracting the digits r = N % 10 ; # Incrementing the frequency if r in occ: occ[r] + = 1 else : occ[r] = 1 N = N / / 10 # Iterating the hashmap for i in occ.keys(): # Check if frequency of digit # is equal to its value or not if (i ! = occ[i]): print ( "No" ); return ; print ( "Yes" ); N = 3331 ; check(N); # This code is contributed by saurabh_jaiswal. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to check if the number // is valid or not public static void check( int N) { // Stores the frequencies // of digits Dictionary< int , int > occ = new Dictionary< int , int >(); while (N > 0) { // Extracting the digits int r = N % 10; if (occ.ContainsKey(r)) { // If char is present in charCountMap, // incrementing it's count by 1 occ[r] = occ[r] + 1; } else { // If char is not present in charCountMap, // putting this char to charCountMap with 1 // as it's value occ.Add(r, 1); } N = N / 10; } foreach ( int key in occ.Keys) { if (key != occ[key]) { Console.Write( "NO" ); return ; } } Console.Write( "Yes" ); } // Driver code public static void Main() { int N = 3331; check(N); } } // This code is contributed by Saurabh Jaiswal |
Javascript
<script> // Javascript program for the above approach // Function to check if the number // is valid or not function check(N) { // Stores the frequencies // of digits let occ = new Map(); while (N > 0) { // Extracting the digits let r = N % 10; // Incrementing the frequency if (occ.has(r)){ occ.set(r, occ.get(r) + 1) } else { occ.set(r, 1) } N = Math.floor(N / 10); } // Iterating the hashmap for (i of occ) { // Check if frequency of digit // is equal to its value or not if (i[0] != i[1]) { document.write( "No<br>" ); return ; } } document.write( "Yes<br>" ); } let N = 3331; check(N); </script> |
Output
Yes
Time Complexity: O(D), D = number of digits in N
Auxiliary Space: O(D)