# Max count of N using digits of M such that 2 and 5, and, 6 and 9 can be treated as same respectively

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:2Explanation: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.

- If the character
- 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
- 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**.

- Let each object in the map is
- After completing the above steps, print the value of
**cnt**as the result.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `int` `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.size();` ` ` `// 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-` `'a'` `;` ` ` `// Insert in the map` ` ` `if` `(mymap.find(c_int)!=mymap.end())` ` ` `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.find(rem) != rems.end())` ` ` `rems[rem] += 1 ;` ` ` `else` ` ` `rems[rem] = 1;` ` ` `n = n / 10;` ` ` `}` ` ` `// Store the resultant count` ` ` `int` `cnt = 1e8;` ` ` `// 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.find(key)==mymap.end())` ` ` `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 Code` `int` `main()` `{` ` ` `int` `N = 56;` ` ` `string M = ` `"245769"` `;` ` ` `cout<<solve(N, M)<<endl;` ` ` `return` `0;` `}` `// This code is contributed by dwivediyash` |

## Java

`// Java program for the above approach` `import` `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));` ` ` `}` `}` |

## 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 string` `function` `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 Code` `let 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)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.