Patching Array ใน C++

สมมติว่าเรามีตัวเลขอาร์เรย์และตัวเลขหนึ่งตัว เราสามารถเพิ่มองค์ประกอบในอาร์เรย์ เพื่อให้ตัวเลขใดๆ ในช่วง [1, n] (รวมทั้งสองอย่าง) เกิดขึ้นได้จากผลรวมขององค์ประกอบบางอย่างในอาร์เรย์ เราต้องหาจำนวนแพตช์ที่จำเป็นขั้นต่ำ ดังนั้นเมื่ออาร์เรย์เป็นเหมือน [1,4] และตัวเลขที่กำหนดคือ n =7 ดังนั้นเอาต์พุตจะเป็น 1 เนื่องจากในตอนแรก ตัวเลขคือ [1], [4] และ [1,4] =5 ตอนนี้ถ้าเราบวก 2 ลงในอาร์เรย์ แล้ว nums จะเป็น [1], [2], [4], [1,2], [1,4],[2,4], [1,2,4] ดังนั้นผลรวม ค่าจะเป็น 1, 2, 4, 3, 5, 6, 7 ตามลำดับ

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

• req :=1, i :=0, ret :=0

• ในขณะที่ req <=n ทำ -

  • ถ้าฉัน <ขนาดของ nums และ nums[i] <=req แล้ว

    • req =req + nums[i]

    • เพิ่มขึ้น 1

  • มิฉะนั้น

    • req =req + req

    • เพิ่มขึ้น 1

• รีเทิร์น

ตัวอย่าง

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minPatches(vector<int>& nums, int n) {
      long long int req = 1;
      int i = 0;
      int ret = 0;
      while(req <= n){
         if(i < nums.size() && nums[i] <= req){
            req += nums[i];
            i++;
         } else {
            req += req;
            ret++;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,4};
   cout << (ob.minPatches(v, 7));
}

อินพุต

{1,4}

ผลลัพธ์

1