การแยกตัวประกอบขั้นต่ำใน C++

สมมติว่าเรามีจำนวนเต็มบวก x เราต้องหาจำนวนเต็มบวกที่เล็กที่สุด b ซึ่งการคูณของแต่ละหลักเท่ากับ x หากเราไม่มีคำตอบดังกล่าว ให้คืนค่า 0

ดังนั้นหากอินพุตเท่ากับ 48 เอาต์พุตจะเป็น 68

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ret :=0, mul :=1

• ถ้า <2 แล้ว:

  • กลับ

• สำหรับการเริ่มต้น i :=9 เมื่อ i>=2 อัปเดต (ลด i โดย 1) ทำ -

  • ในขณะที่ mod i เหมือนกับ 0, do -

    • ret :=i * mul + ret

    • mul :=mul * 10

    • a :=a / i

• return (ถ้า a <2 และ ret

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   int smallestFactorization(int a) {
      lli ret = 0;
      lli mul = 1;
      if (a < 2)
         return a;
      for (lli i = 9; i >= 2; i--) {
         while (a % i == 0) {
            ret = i * mul + ret;
            mul *= 10;
            a /= i;
         }
      }
      return a < 2 && ret < INT_MAX ? ret : 0;
   }
};
main(){
   Solution ob;
   cout << (ob.smallestFactorization(48));
}

อินพุต

48

ผลลัพธ์

68