ตัวดำเนินการน้อยที่สุดเพื่อแสดงจำนวนใน C++

คำอธิบายปัญหา

ให้จำนวนเต็มบวก x เขียนนิพจน์รูป x op1 x op2 x op3 ... โดย op ∈ {+,-,*,/} กฎ:

• / คืนค่าจำนวนตรรกยะ (ไม่ใช่ integer division)
• ไม่มีวงเล็บ
• ลำดับการดำเนินการปกติ: */ ก่อน +-
• ห้ามใช้ unary negation

หาจำนวนตัวดำเนินการน้อยที่สุดเพื่อให้นิพจน์มีค่าเท่ากับ target

ตัวอย่าง

x = 4, target = 15 → Output: 3
นิพจน์: 4*4 - 4/4 = 16 - 1 = 15 (3 ตัวดำเนินการ)

แนวทางแก้ปัญหา: Recursive + Greedy

1. กรณีฐาน: target == x → 0 ตัวดำเนินการ
2. ถ้า x > target: min((x-target)*2, target*2-1)
   • x-target: ใช้การลบ (x/x + x/x + ...)
   • target: ใช้การบวก (x/x + x/x + ...)
3. หา sum = xᵗ ใกล้ target มากที่สุด (sum ≥ target)
4. ถ้า sum == target → คืน t
5. พิจารณา 2 ทางเลือก:
   • l: ใช้ sum/x เป็นฐาน แล้วบวก (target - sum/x) → cost = leastOps(x, target - sum/x) + t - 1
   • r: ใช้ sum เป็นฐาน แล้วลบ (sum - target) → cost = leastOps(x, sum - target) + t (ถ้า sum-target < target)
6. คืน 1 + min(l, r) (บวก 1 สำหรับ * หรือ / ที่เชื่อม)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;

class Solution {
public:
    int leastOpsExpressTarget(int x, int target) {
        if(target == x) return 0;
        if(x > target) {
            return min((x-target)*2, target*2-1);
        }
        lli sum = x;
        int t = 0;
        while(sum < target) { sum *= x; t++; }
        if(sum == target) return t;
        
        int l = INT_MAX, r = INT_MAX;
        if(sum - target < target)
            r = leastOpsExpressTarget(x, sum - target) + t;
        l = leastOpsExpressTarget(x, target - sum/x) + t - 1;
        return min(l, r) + 1;
    }
};

ความซับซ้อน

• เวลา: O(logₓ target) เนื่องจากลดปัญหาลงเรื่อยๆ
• พื้นที่: O(logₓ target) สำหรับ recursion stack