Given an integer N, and the string integer M, the task is to find the total count to make N by using the digits of string M. Also, digit 2 can be treated as digit 5, and digit 6 can be treated as digit 9 and vice versa and each digit from the string M can be used at most once.
Examples:
Input: N = 6, M = “245769”
Output: 2
Explanation: Digits 5 and 6 are used to form the number 56. iop[The digits 2 and 9 are used to form the number 56. As 2 is treated as 5 and 9 is treated as 6.Input: N = 25, M = “55”
Output: 1
Approach: The given problem can be solved by Hashing. Follow the steps below to solve the problem:
- Create an empty hashmap, say map to store the frequency of the digits of the given string M.
- Create a variable, say, len to store the length of the string.
- Traverse the given string S using the variable i and Iterate until the value of i is less than len and perform the following steps:
- If the character S[i] is equal to ‘5’, then change it to ‘2’.
- If the character S[i] is equal to ‘9’, then change it to ‘6’.
- If the character is present in the mymap, then change the frequency as mymap.put(x, map.get(x)+1).
- Otherwise, insert the character in the map with frequency 1 as mymap.put(x, 1).
- After adding the frequency to the map, increment i and continue to the next iteration.
- Create an empty hashmap, say rems to store the digits of the number N.
- Iterate until the value of N is greater than 0, and perform the following steps:
- Create a variable, say rem to store the last digit of N by using the modulus operator as N%10.
- If rem is equal to 5, then change it to 2.
- If rem is equal to 9, then change it to 6.
- If the rem is present in the rems map, then increase the frequency by 1as rems.put(rem, rems.get(rem)+1).
- Otherwise, insert it to the rems map as rems.put(rem, 1).
- Divide N by 10.
- Create a variable, say cnt to store the maximum count of the number N that can be formed using the given digits of string M.
- Traverse through the map rems, and perform the following steps:
- Let each object in the map is ele.
- Check if the key from ele is present in the frequency map of string mymap.
- If not present, the return 0 (The number N cannot be formed if a digit from N is not present in string M).
- Calculate the count by dividing the frequency of the key in mymap with the frequency in rems map as mymap.get(key)/ele.getValue().
- Update the minimum value from all iterations in cnt.
- After completing the above steps, print the value of cnt as the result.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <climits>#include <cmath>#include <iostream>#include <map>using namespace std;// C++ function to find the count of numbers that can be// formed using the given digits in the stringint solve(int n, string str){ // Store the frequency of digits from the given string M map<int, int> mymap; // Store length of the string M int len = str.length(); // Loop to traverse the string for (int i = 0; i < len; i++) { char c = str[i]; // Replace 5 with 2 if (c == '5') c = '2'; // Replace 9 with 6 else if (c == '9') c = '6'; // Get the int form of the current character in the // string int c_int = c - '0'; // Insert in the map if (mymap.count(c_int)) mymap[c_int] += 1; else mymap[c_int] = 1; } // Store all the digits of the required number N map<int, int> rems; // Loop to get all the digits from the number N while (n > 0) { // Get the last digit as the remainder int rem = n % 10; // Replace 5 with 2 if (rem == 5) rem = 2; // Replace 9 with 6 if (rem == 9) rem = 6; // Insert the remainders in the rems map if (rems.count(rem)) rems[rem] += 1; else rems[rem] = 1; n = floor(n / 10); } // Store the resultant count int cnt = INT_MAX; // Iterate through the rems map for (auto ele : rems) { // Get the key which is a digit from the number N to // be formed int key = ele.first; // If not present in the string M, number N that // cannot be formed if (!mymap.count(key)) return 0; // Divide the frequency of the digit from the string // M with the frequency of the current remainder int temp = mymap[key] / ele.second; // Choose the minimum cnt = min(cnt, temp); } // Return the maximum count return cnt;}// Driver codeint main(){ int N = 56; string M = "245769"; cout << solve(N, M) << endl; return 0;}// This code is contributed by phasing17 |
Java
// Java program for the above approachimport java.util.HashMap;import java.util.Map;public class GFG { // Function to find the count of // numbers that can be formed using // the given digits in the string int solve(int n, String str) { // Store the frequency of digits // from the given string M HashMap<Integer, Integer> mymap = new HashMap<>(); // Store length of the string M int len = str.length(); // Loop to traverse the string for (int i = 0; i < len; i++) { char c = str.charAt(i); // Replace 5 with 2 if (c == '5') c = '2'; // Replace 9 with 6 else if (c == '9') c = '6'; // Get the int form of // the current character // in the string int c_int = Integer.parseInt( String.valueOf(c)); // Insert in the map if (mymap.containsKey(c_int)) mymap.put( c_int, mymap.get(c_int) + 1); else mymap.put(c_int, 1); } // Store all the digits of the // required number N HashMap<Integer, Integer> rems = new HashMap<>(); // Loop to get all the digits // from the number N while (n > 0) { // Get the last digit as // the remainder int rem = n % 10; // Replace 5 with 2 if (rem == 5) rem = 2; // Replace 9 with 6 if (rem == 9) rem = 6; // Insert the remainders // in the rems map if (rems.containsKey(rem)) rems.put(rem, rems.get(rem) + 1); else rems.put(rem, 1); n = n / 10; } // Store the resultant count int cnt = Integer.MAX_VALUE; // Iterate through the rems map for (Map.Entry<Integer, Integer> ele : rems.entrySet()) { // Get the key which is // a digit from the number // N to be formed int key = ele.getKey(); // If not present in the // string M, number N that // cannot be formed if (!mymap.containsKey(key)) return 0; // Divide the frequency of // the digit from the string // M with the frequency of // the current remainder int temp = mymap.get(key) / ele.getValue(); // Choose the minimum cnt = Math.min(cnt, temp); } // Return the maximum count return cnt; } // Driver Code public static void main(String args[]) { GFG obj = new GFG(); int N = 56; String M = "245769"; System.out.println(obj.solve(N, M)); }} |
Python3
# Python3 program for the above approach# Function to find the count of# numbers that can be formed using# the given digits in the stringdef solve(n, str): # Store the frequency of digits # from the given string M mymap = dict() # Store length of the string M length = len(str) # Loop to traverse the string for i in range(length): c = str[i] # Replace 5 with 2 if c == "5": c = "2" # Replace 9 with 6 elif c == "9": c = "6" # Get the int form of # the current character # in the string c_int = int(c) # Insert in the map if c_int in mymap: mymap[c_int] += 1 else: mymap[c_int] = 1 # Store all the digits of the # required number N rems = dict() # Loop to get all the digits # from the number N while n > 0: # Get the last digit as # the remainder rem = n % 10 # Replace 5 with 2 if rem == 5: rem = 2 # Replace 9 with 6 if rem == 9: rem = 6 # Insert the remainders # in the rems map if rem in rems: rems[rem] += 1 else: rems[rem] = 1 n = n // 10 # Store the resultant count cnt = float('inf') # Iterate through the rems map for key, value in rems.items(): # If not present in the # string M, number N that # cannot be formed if key not in mymap: return 0 # Divide the frequency of # the digit from the string # M with the frequency of # the current remainder temp = mymap[key] / value # Choose the minimum cnt = min(cnt, temp) # Return the maximum count return int(cnt)# Driver CodeN = 56M = "245769"print(solve(N, M))# This code is contributed by phasing17. |
C#
using System;using System.Collections;using System.Linq;using System.Collections.Generic;public class GFG{ static public void Main (){ GFG obj = new GFG(); int N = 56; String M = "245769"; Console.WriteLine(obj.solve(N, M)); } public int solve(int N, String M){ // Store the frequency of digits // from the given string M Dictionary<int,int> mymap = new Dictionary<int,int>(); // Store length of the string M int len = M.Length; // Loop to traverse the string var cArr = M.ToCharArray(); for (int i = 0; i < len; i++) { char c = cArr[i]; // Replace 5 with 2 if (c == '5') c = '2'; // Replace 9 with 6 else if (c == '9') c = '6'; // Get the int form of // the current character // in the string int c_int = int.Parse(c.ToString()); // Insert in the map if (mymap.ContainsKey(c_int)) mymap[c_int]=(mymap[c_int] + 1); else mymap.Add(c_int, 1); } // Store all the digits of the // required number N Dictionary<int,int> rems = new Dictionary<int,int>(); // Loop to get all the digits // from the number N while (N > 0) { // Get the last digit as // the remainder int rem = N % 10; // Replace 5 with 2 if (rem == 5) rem = 2; // Replace 9 with 6 if (rem == 9) rem = 6; // Insert the remainders // in the rems map if (rems.ContainsKey(rem)) rems[rem]= rems[rem] + 1; else rems.Add(rem, 1); N = N / 10; } // Store the resultant count int cnt = int.MaxValue; // Iterate through the rems map foreach (var ele in rems) { // Get the key which is // a digit from the number // N to be formed int key = ele.Key; // If not present in the // string M, number N that // cannot be formed if (!mymap.ContainsKey(key)) return 0; // Divide the frequency of // the digit from the string // M with the frequency of // the current remainder int temp = (int)mymap[key] / (int)ele.Value; // Choose the minimum cnt = Math.Min(cnt, temp);}// Return the maximum countreturn cnt; } }// This code is contributed by el_genius. |
Javascript
<script>// Javascript program for the above approach// Function to find the count of// numbers that can be formed using// the given digits in the stringfunction solve(n, str) { // Store the frequency of digits // from the given string M let mymap = new Map(); // Store length of the string M let len = str.length; // Loop to traverse the string for (let i = 0; i < len; i++) { let c = str.charAt(i); // Replace 5 with 2 if (c == "5") c = "2"; // Replace 9 with 6 else if (c == "9") c = "6"; // Get the int form of // the current character // in the string let c_int = parseInt(c); // Insert in the map if (mymap.has(c_int)) mymap.set(c_int, mymap.get(c_int) + 1); else mymap.set(c_int, 1); } // Store all the digits of the // required number N let rems = new Map(); // Loop to get all the digits // from the number N while (n > 0) { // Get the last digit as // the remainder let rem = n % 10; // Replace 5 with 2 if (rem == 5) rem = 2; // Replace 9 with 6 if (rem == 9) rem = 6; // Insert the remainders // in the rems map if (rems.has(rem)) rems.set(rem, rems.get(rem) + 1); else rems.set(rem, 1); n = Math.floor(n / 10); } // Store the resultant count let cnt = Number.MAX_SAFE_INTEGER; // Iterate through the rems map for (let ele of rems) { // Get the key which is // a digit from the number // N to be formed let key = ele[0]; // If not present in the // string M, number N that // cannot be formed if (!mymap.has(key)) return 0; // Divide the frequency of // the digit from the string // M with the frequency of // the current remainder let temp = mymap.get(key) / ele[1]; // Choose the minimum cnt = Math.min(cnt, temp); } // Return the maximum count return cnt;}// Driver Codelet N = 56;let M = "245769";document.write(solve(N, M));// This code is contributed by gfgking.</script> |
Output
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
