จำนวนสูงสุดที่มีผลิตภัณฑ์แฟคทอเรียลหลักเดียวกันใน C++

ภารกิจคือการหาจำนวนสูงสุดโดยไม่มีศูนย์นำหน้าหรือต่อท้าย หรือจำนวนที่ผลคูณของแฟคทอเรียลของหลักนั้นเท่ากับผลคูณของแฟกทอเรียลของหลักของตัวเลขที่ระบุ N

ตอนนี้มาทำความเข้าใจสิ่งที่เราต้องทำโดยใช้ตัวอย่าง -

ป้อนข้อมูล − N =4912

ผลผลิต − 73332222

คำอธิบาย − 4! * 9! * 1! * 2! =7! * 3! * 3! * 3! * 2! * 2! *2! *2! =17,418,240

ป้อนข้อมูล − N =340

ผลผลิต − 3322

แนวทางที่ใช้ในโปรแกรมด้านล่างดังนี้

• เพื่อให้ได้คำตอบสูงสุด เราจะต้องแสดงจำนวนที่กำหนดเป็นผลคูณของแฟคทอเรียลของจำนวนเฉพาะ

  หากตัวเลขที่ระบุมีเพียงศูนย์และอีกตัวหนึ่ง จะไม่สามารถค้นหาผลลัพธ์ได้

• ในฟังก์ชัน MaxNum() ให้สร้างตัวแปร total_digits ของประเภท int เพื่อเก็บจำนวนหลักทั้งหมด และยังเริ่มต้นอาร์เรย์อื่น Frq[] ={0} ของประเภท int เพื่อเก็บความถี่ของตัวเลขที่เกิดขึ้นแต่ละตัว

• วนจาก i=0 ถึง i

• หากตัวเลขปัจจุบันเป็นจำนวนเฉพาะ ให้เพิ่ม 1 ไปยังตำแหน่งของอาร์เรย์ Frq[]

• ตัวเลขอื่นที่ไม่ใช่จำนวนเฉพาะ จากนั้นให้ตรวจสอบว่าคำสั่ง if เป็น 4, 6, 8 หรือ 9 แยกจากกันหรือไม่ จากนั้นแยกออกเป็นแฟกทอเรียลเฉพาะพื้นฐานและเพิ่มความถี่ตามลำดับ

• สร้างสตริงว่าง 'ans' เพื่อเก็บคำตอบสุดท้าย

• ก่อนดำเนินการขั้นตอนสุดท้าย ให้ตรวจสอบว่าตัวเลขมีเพียงตัวเดียวและเลขศูนย์เท่านั้น หากเป็นเช่นนั้น ให้คืนค่าสตริงเดิม ไม่เช่นนั้นให้ไปยังขั้นตอนถัดไป

• วนรอบจาก i=9 ถึง i>=2 เริ่มต้นตัวแปร C =Frq[i] ของประเภท int และภายใน for ลูปสร้างลูปในขณะที่มีเงื่อนไขในขณะที่ (C--) ซึ่งใส่ ans+=(char)(i+48) เพื่อเก็บคำตอบสุดท้ายลงในสตริง ตอบ

ตัวอย่าง

#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;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น เราจะได้ผลลัพธ์ดังต่อไปนี้ -

3322