C++-এ প্যাচিং অ্যারে (Patching Array) সমস্যা

প্যাচিং অ্যারে সমস্যা

একটি সর্ট করা অ্যারে nums এবং একটি সংখ্যা n দেওয়া আছে। অ্যারেতে কিছু সংখ্যা যোগ করে (প্যাচ করে) যাতে [1, n] রেঞ্জের সব সংখ্যা অ্যারের কিছু উপাদানের যোগফল হিসেবে তৈরি করা যায়। ন্যূনতম কতটি প্যাচ দরকার?

উদাহরণ: nums=[1,4], n=7 → প্যাচ ১টি (সংখ্যা ২ যোগ করলে সব ১-৭ তৈরি হয়)

সমাধানের পদ্ধতি (লালচী / Greedy)

• req := 1 (এখন পর্যন্ত আমরা [1, req-1] রেঞ্জ কভার করেছি)
• i := 0, ret := 0
• while req ≤ n:
  • যদি i < nums.size() && nums[i] ≤ req: req += nums[i]; i++ (বিদ্যমান সংখ্যা ব্যবহার করুন)
  • অন্যথায়: req += req; ret++ (নতুন সংখ্যা req যোগ করুন)
• ret ফেরত দিন

C++ কোড উদাহরণ

{1,4}

আউটপুট

1