สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และอีกค่าหนึ่งคือ k เราต้องหาจำนวนตัวเลขขั้นต่ำที่เราต้องใส่ลงใน num เพื่อให้เราสามารถสร้างตัวเลขใดๆ จาก [1, k] โดยใช้เซตย่อยเป็น nums
ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[3, 5], k =6 ผลลัพธ์จะเป็น 2 เนื่องจากเราต้องแทรก 1, 2 เราจึงได้ :1 =[1], 2 =[2 ], 3 =[3], 4 =[1, 3], 5 =[5], 6 =[1, 5].
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- เรียงลำดับจำนวนอาร์เรย์
- sum :=0, next :=1, ret :=0
- สำหรับทั้งหมด i ใน nums
- ต่อไป
- ถ้าผลรวม>=k แล้ว:
- ออกมาจากวงจร
- sum :=sum + ถัดไป
- ถัดไป :=ผลรวม + 1
- (เพิ่มการถอนคืนโดย 1)
- ถ้าผลรวม>=k แล้ว:
- ออกมาจากวงจร
- sum :=sum + i
- ถัดไป :=ผลรวม + 1
- sum :=sum + ถัดไป
- ถัดไป :=ผลรวม + 1
- (เพิ่มการถอนคืนโดย 1)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include using namespace std; class Solution { public: int solve(vector& nums, int k) { sort(nums.begin(), nums.end()); int sum = 0; int next = 1; int ret = 0; for (int i : nums) { while (next < i) { if (sum >= k) break; sum += next; next = sum + 1; ret++; } if (sum >= k) break; sum += i; next = sum + 1; } while (next <= k) { sum += next; next = sum + 1; ret++; } return ret; } }; int solve(vector& nums, int k) { return (new Solution())->solve(nums, k); } int main(){ vector v = {3, 5}; int k = 6; cout << solve(v, k); }
อินพุต
[3, 5], 6
ผลลัพธ์
2