Count of digits in N and M that are same but present on different indices
Given two numbers N and M, the task is to find the count of digits in N and M that are the same but present on different indices.
Examples:
Input: N = 123, M = 321
Output: 2
Explanation: Digit 1 and 3 satisfies the conditionInput: N = 123, M = 111
Output: 0
Approach: The problem can be solved using hashing and two-pointer approach.
- Convert N and M to string for ease of traversal
- Now create 2 hash of size 10 to store frequency of digits in N and M respectively
- Now traverse a loop from 0-9 and:
- Add min of hashN[i] and hashM[i] to a variable count
- Now traverse the numbers using two pointers to find the count of digits that are same and occur on same indices in both N and M. Store the count in variable same_dig_cnt
- Now return the final count as count – same_dig_cnt
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; int countDigits( int N, int M) { // Convert N and M to string // for ease of traversal string a = to_string(N), b = to_string(M); // Create 2 hash of size 10 // to store frequency of digits // in N and M respectively vector< int > hashN(10, 0); for ( char c : a) hashN++; vector< int > hashM(10, 0); for ( char c : b) hashM++; int count = 0, same_dig_cnt = 0; // Count of common digits // irrespective of their positions for ( int i = 0; i < 10; i++) count += min(hashN[i], hashM[i]); // Find the count of digits // that are same and occur on same indices // in both N and M. // Store the count in variable same_dig_cnt for ( int i = 0; i < a.length() && b.length(); i++) if (a[i] == b[i]) same_dig_cnt++; // Remove the count of digits that are // not at same indices in both numbers count -= same_dig_cnt; return count; } // Driver code int main() { int N = 123, M = 321; cout << countDigits(N, M); return 0; } |
Java
// Java implementation of the above approach class GFG { static int countDigits( int N, int M) { // Convert N and M to string // for ease of traversal String a = Integer.toString(N), b = Integer.toString(M); // Create 2 hash of size 10 // to store frequency of digits // in N and M respectively int [] hashN = new int [ 10 ]; for ( int i = 0 ; i < 10 ; i++) { hashN[i] = 0 ; } for ( char c : a.toCharArray()) { hashN++; } int [] hashM = new int [ 10 ]; for ( int i = 0 ; i < 10 ; i++) { hashM[i] = 0 ; } for ( char c : a.toCharArray()) { hashM++; } int count = 0 , same_dig_cnt = 0 ; // Count of common digits // irrespective of their positions for ( int i = 0 ; i < 10 ; i++) count += Math.min(hashN[i], hashM[i]); // Find the count of digits // that are same and occur on same indices // in both N and M. // Store the count in variable same_dig_cnt for ( int i = 0 ; i < a.length() && i < b.length(); i++) if (a.charAt(i) == b.charAt(i)) same_dig_cnt++; // Remove the count of digits that are // not at same indices in both numbers count -= same_dig_cnt; return count; } // Driver code public static void main(String args[]) { int N = 123 , M = 321 ; System.out.println(countDigits(N, M)); } } // This code is contributed by gfgking |
Python3
# Python code for the above approach def countDigits(N, M): # Convert N and M to string # for ease of traversal a = str (N) b = str (M) # Create 2 hash of size 10 # to store frequency of digits # in N and M respectively hashN = [ 0 ] * 10 for c in range ( len (a)): hashN[ ord (a) - ord ( '0' )] + = 1 hashM = [ 0 ] * 10 for c in range ( len (b)): hashM[ ord (b) - ord ( '0' )] + = 1 count = 0 same_dig_cnt = 0 ; # Count of common digits # irrespective of their positions for i in range ( 10 ): count + = min (hashN[i], hashM[i]); # Find the count of digits # that are same and occur on same indices # in both N and M. # Store the count in variable same_dig_cnt i = 0 while (i < len (a) and len (b)): if (a[i] = = b[i]): same_dig_cnt + = 1 i + = 1 # Remove the count of digits that are # not at same indices in both numbers count - = same_dig_cnt; return count; # Driver code N = 123 M = 321 ; print (countDigits(N, M)); # This code is contributed by Saurabh Jaiswal |
C#
// C# implementation of the above approach using System; using System.Collections; class GFG { static int countDigits( int N, int M) { // Convert N and M to string // for ease of traversal string a = N.ToString(), b = M.ToString(); // Create 2 hash of size 10 // to store frequency of digits // in N and M respectively int []hashN = new int [10]; for ( int i = 0; i < 10; i++) { hashN[i] = 0; } foreach ( char c in a) { hashN++; } int []hashM = new int [10]; for ( int i = 0; i < 10; i++) { hashM[i] = 0; } foreach ( char c in a) { hashM++; } int count = 0, same_dig_cnt = 0; // Count of common digits // irrespective of their positions for ( int i = 0; i < 10; i++) count += Math.Min(hashN[i], hashM[i]); // Find the count of digits // that are same and occur on same indices // in both N and M. // Store the count in variable same_dig_cnt for ( int i = 0; i < a.Length && i < b.Length; i++) if (a[i] == b[i]) same_dig_cnt++; // Remove the count of digits that are // not at same indices in both numbers count -= same_dig_cnt; return count; } // Driver code public static void Main() { int N = 123, M = 321; Console.Write(countDigits(N, M)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach function countDigits(N, M) { // Convert N and M to string // for ease of traversal let a = (N).toString(), b = (M).toString(); // Create 2 hash of size 10 // to store frequency of digits // in N and M respectively let hashN = new Array(10).fill(0); for (let c = 0; c < a.length; c++) hashN[a.charCodeAt(0) - '0' .charCodeAt(0)]++; let hashM = new Array(10).fill(0); for (c = 0; c < b.length; c++) hashM[b.charCodeAt(0) - '0' .charCodeAt(0)]++; let count = 0, same_dig_cnt = 0; // Count of common digits // irrespective of their positions for (let i = 0; i < 10; i++) count += Math.min(hashN[i], hashM[i]); // Find the count of digits // that are same and occur on same indices // in both N and M. // Store the count in variable same_dig_cnt for (let i = 0; i < a.length && b.length; i++) if (a[i] == b[i]) same_dig_cnt++; // Remove the count of digits that are // not at same indices in both numbers count -= same_dig_cnt; return count; } // Driver code let N = 123, M = 321; document.write(countDigits(N, M)); // This code is contributed by Potta Lokesh </script> |
Output
2
Time Complexity: O(D), where D is the max count of digits in N or M
Auxiliary Space: O(D), where D is the max count of digits in N or M
Contact Us