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

Photo of Namachila Namachila Send an email 4 minutes ago
0 0 9 minutes read

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 string
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.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 code
int 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 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));


    }


}








































Python3


















 






 




 



























# Python3 program for the above approach


 


# Function to find the count of


# numbers that can be formed using


# the given digits in the string


def 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 Code


 


N = 56


M = "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 count


return 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 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)





                                            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 zambiatek!







			
		


				

			

				

						
							Photo of Namachila
						
					Namachila
						
							
							Send an email
						
					4 minutes ago
0 0  9 minutes read 


		

					

		


		

		

		

		
	


	
	


		
		


								

						
							Photo of Namachila						
					

					
			


											
Namachila

						
				

									


							

			

		

		


	





			

			
			

			

	

				


					

						
Related Articles

					


					


					
							


								
			
								
Count of numbers in given range L to R which are present in a Matrix


								
4 minutes ago
							


						
							


								
			
								
Prove that Dense Subgraph is NP Complete by Generalisation


								
4 minutes ago
							


						
							


								
			
								
Javascript Program To Write Your Own atoi()


								
4 minutes ago
							


						
							


								
			
								
Check if elements of Linked List are present in pair


								
4 minutes ago
							


						
					

				


				


		

		
	

		
Leave a Reply 
Your email address will not be published. Required fields are marked *
 
 



 


 


 


	

	

	



	


	




	

	
	
	






		

		
		
			
			Back to top button