Menggunakan nombor M, kiraan maksimum ialah N, di mana 2 dan 5 dan 6 dan 9 boleh dianggap sama antara satu sama lain

Kiraan maksimum ialah kiraan maksimum yang mungkin. Di sini, kita diberi integer N dan rentetan integer M. Tugas kita ialah membentuk nombor N menggunakan digit integer M dan mengembalikan kiraan maksimum. Pada masa yang sama, kita boleh memikirkan 2 dan 5 sebagai nombor yang sama, dan 6 dan 9 sebagai nombor yang sama.

Contoh Contoh

Masukkan 1

N = 29
M = "2569783"
Output 1: 2

Penjelasan − Oleh kerana 5 dan 2 adalah sama dan 6 dan 9 adalah sama, kita mempunyai dua '2' dan dua '9's. Oleh itu, kiraan maksimum menggunakan digit rentetan M (2596783) untuk membentuk nombor N (29) ialah 2.

Masukkan 2

N = 999
M = 6666925
Output 2: 1

Kaedah

Jom bincang kaedah di bawah langkah demi langkah-

• Pertama, kami akan mencipta fungsi yang dipanggil 'maxCountOfN' yang akan mengambil rentetan 'M' dan nombor 'N' yang diberikan sebagai parameter dan akan mengembalikan integer yang diperlukan 'maxCount' sebagai nilai pulangan.

• Dalam fungsi ini, kami akan mencipta peta hash 'mp' untuk menyimpan kekerapan setiap nombor dalam rentetan 'M'.

• Kami mentakrifkan pembolehubah 'len' untuk menyimpan saiz rentetan 'M'.

• Lintas rentetan 'M' bermula dari indeks 'i = 0' sehingga kurang daripada atau sama dengan 'len', dan lakukan operasi berikut di bawah gelung ini:

• Jika nombor yang kita dapat ialah '2', kita tukarkan kepada '5'.

• Jika kita mendapat nombor sebagai '6', kita tukarkannya kepada '9'.

• Kira kekerapan setiap nombor dalam peta 'mp' sebagai pasangan integer aksara.

• Buat peta cincang 'mpN' lain untuk menyimpan kekerapan nombor N

• Gunakan gelung sementara untuk lelaran melalui nombor 'N' sehingga N lebih besar daripada 0, dan lakukan operasi berikut di bawah gelung ini -

• Buat 'rem' integer untuk menyimpan elemen terakhir nombor

• Semak sama ada 2 dan tukarkan kepada 5

• Semak sama ada rem ialah 6 dan tukarkannya kepada 9

• Kira kekerapan setiap nombor dalam peta 'mpN' sebagai pasangan integer aksara. Iaitu untuk menyimpan integer sebagai aksara dalam peta, seperti 'mpN[rem + '0']'.

• Kurangkan N kepada N%10 untuk mengeluarkan digit terakhir nombor

• Kami mencipta pembolehubah 'maxCount' yang menyimpan 'INT_MAX'.

• Akhir sekali, kami mengulangi peta 'mpN' untuk mencari kiraan maksimum N dan melakukan perkara berikut di bawah gelung ini -

• Simpan bilangan digit dalam ‘kunci’ pembolehubah

• Semak sama ada kunci wujud dalam peta rentetan, jika tidak hadir bermakna kita tidak boleh mencipta nombor 'N' menggunakan nombor rentetan 'M', kita kembalikan '0'.

• Cipta pembolehubah dalam 'tempCount' pembolehubah di mana kita menyimpan nilai (membahagikan kekerapan nombor dalam rentetan M dengan kekerapan nombor semasa dalam N).

• Dalam maxCount, kami menyimpan nilai minimum tempCount dan maxCount kerana adalah mungkin untuk menjana nombor 'N' hanya jika setiap digit nombor 'N' muncul dalam rentetan 'M'

• Pulangan maxCount

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

#include <bits/stdc++.h>
using namespace std;
int maxCountOfN(int N, string M){
   map< char, int >mp; //created hashmap to store the frequency of each digit of //string
   int len = M.size(); // getting the size of the string     
   // iterating string using for loop 
   for(int i=0;i<len;i++){
      if(M[i] == '2'){
         M[i] = '5'; // replace 2 with 5
      }
      else if(M[i] == '6'){ 
         M[i] = '9'; // replace 6 with 9
      }
      mp[M[i]]++; //count frequency of digit of string
   }    
   // creating another hashmap to store the frequency of digit of the number N
   map<char, int>mpN;      
   // iterating number 'N' using while loop     
   while(N > 0){
      int rem = N % 10; // Get the last digit as the remainder        
      //Replace 2 with 5
      if(rem == 2){
         rem = 5;
      }
      //Replace 6 with 9
      if(rem == 6){
         rem = 9;
      }        
      mpN[rem + '0']++; //count frequency of digit of number        
      N = N / 10;
   }    
   int maxCount = INT_MAX;
   //Trvaerse the hashmap of the number to get the maxCount
   for(auto el : mpN){
      // Get the key which is a digit from the number N to be formed
      int key = el.first; 
      // If the key is not present in the string M, then the number N cannot be formed
      if (!mp.count(key))
      return 0; 
      // Divide the frequency of the digit from the string M with the frequency of the current digit of N
      int tempCount = mp[key] / el.second; 
      // Choose the minimum
      maxCount = min(maxCount, tempCount);
   }    
   // returning the maximum count 
   return maxCount;
}
// main function 
int main(){    
   int N = 29; // given number
   string M = "2569783";// given string    
   // calling the function to get a maximum count of N 
   int maxCount = maxCountOfN(N, M);   
   cout<<"The max count of making the number "<< N << " using the digits of the string " << M << " is "<< maxCount<<endl;   
   return 0;
}

Output

The max count of making the number 29 using the digits of the string 2569783 is 2

Kesimpulan

Dalam tutorial ini, kami telah melaksanakan program untuk mencari kiraan Maks N menggunakan digit M supaya 2 dan 5, dan, 6 dan 9 masing-masing boleh dianggap sama Kami telah melaksanakan pendekatan pencincangan seperti yang kami lakukan untuk menyimpan kekerapan dengan kerumitan masa O(N+M) dan kerumitan ruang O(N+M) Di mana M ialah saiz rentetan dan N ialah saiz Nombor.

Atas ialah kandungan terperinci Menggunakan nombor M, kiraan maksimum ialah N, di mana 2 dan 5 dan 6 dan 9 boleh dianggap sama antara satu sama lain. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!