Số tối đa có tích giai thừa cùng một chữ số trong C ++

Được giao nhiệm vụ là tìm số lớn nhất không có số 0 đứng đầu hoặc ở cuối hoặc số đơn vị có tích giai thừa của các chữ số của nó bằng tích giai thừa của các chữ số của số N đã cho.

Bây giờ chúng ta hãy hiểu những gì chúng ta phải làm bằng cách sử dụng một ví dụ -

Đầu vào - N =4912

Đầu ra - 73332222

Giải thích - 4! * 9! * 1! * 2! =7! * 3! * 3! * 3! * 2! * 2! * 2! * 2! =17.418.240

Đầu vào - N =340

Đầu ra - 3322

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Để đạt được câu trả lời tối đa, chúng ta sẽ phải biểu thị số đã cho dưới dạng tích giai thừa của các số nguyên tố.

Nếu số đã cho chỉ chứa các số không và một thì không thể tìm được đầu ra.
Trong hàm MaxNum (), hãy tạo một biến total_digits kiểu int để lưu trữ tổng số chữ số và cũng khởi tạo một mảng khác Frq [] ={0} kiểu int để lưu trữ tần số của mỗi số xuất hiện.
Lặp lại từ i =0 cho đến i
Nếu chữ số hiện tại là số nguyên tố, thì chỉ cần thêm 1 vào vị trí đó của mảng Frq [].
Các chữ số khác không phải là số nguyên tố, sau đó thông qua các câu lệnh if riêng biệt kiểm tra xem nó có phải là 4, 6, 8 hoặc 9 hay không rồi chia nó thành các thừa số nguyên tố cơ bản của nó và tăng tần số cho phù hợp.
Tạo một chuỗi trống "ans" để lưu trữ câu trả lời cuối cùng.
Trước khi tiếp tục bước cuối cùng, hãy kiểm tra xem số đó có chỉ chứa các số một và các số không. Nếu đúng như vậy thì chỉ cần trả lại chuỗi ban đầu, nếu không hãy chuyển sang bước tiếp theo.
Vòng lặp từ i =9 đến i> =2. Khởi tạo một biến C =Frq [i] kiểu int và bên trong vòng lặp for tạo một vòng lặp while với điều kiện while (C--) trong đó đặt ans + =(char) (i + 48) để lưu trữ câu trả lời cuối cùng vào chuỗi ans.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
string MaxNum(string str){
   int total_digits = str.length();
   int Frq[15] = { 0 };
   //Obtaining the frequency of every digit
   for (int i = 0; i < total_digits; i++){
      if (str[i] == '1'|| str[i] == '2'|| str[i] == '3'|| str[i] == '5'|| str[i] == '7'){
         Frq[str[i] - 48] += 1;
      }
      // 4! = 2! * 2! * 3!
      if (str[i] == '4'){
         Frq[2] += 2;
         Frq[3]++;
      }
      // 6! = 5! * 3!
      if (str[i] == '6'){
         Frq[5]++;
         Frq[3]++;
      }
      // 8! = 7! * 2! * 2! * 2!
      if (str[i] == '8'){
         Frq[7]++;
         Frq[2] += 3;
      }
      // 9! = 7! * 3! * 3! * 2!
      if (str[i] == '9'){
         Frq[7]++;
         Frq[3] += 2;
         Frq[2]++;
      }
   }
   string ans = "";
   //If number has only 1 or 0
   if (Frq[1] == total_digits || Frq[0] == total_digits || (Frq[0] + Frq[1]) == total_digits){
      return str;
   }
   else{
      //Maximum number possible
      for (int i = 9; i >= 2; i--){
         int C = Frq[i];
         while (C--){
            ans += (char)(i + 48);
         }
      }
      return ans;
   }
}
//Main function
int main(){
   string str = "340";
   cout << MaxNum(str);
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, chúng ta sẽ nhận được kết quả sau -