C++-এ অ্যারেকে অনন্য করতে ন্যূনতম বৃদ্ধি

ধরুন আমাদের কাছে পূর্ণসংখ্যা A এর একটি অ্যারে রয়েছে, এখানে একটি পদক্ষেপের মধ্যে রয়েছে যে কোনো A[i] বেছে নেওয়া, এবং এটিকে 1 দ্বারা বৃদ্ধি করা। A-তে প্রতিটি মান অনন্য করার জন্য আমাদের সর্বনিম্ন সংখ্যক চাল খুঁজে বের করতে হবে। সুতরাং ইনপুট যদি [3,2,1,2,1,7] এর মত হয়, তাহলে আউটপুট হবে 6, যেমন 6টি মুভের পরে, অ্যারে হতে পারে [3,4,1,2,5,7], এটি 5 বা তার কম চাল দিয়ে দেখানো যেতে পারে যে অ্যারের জন্য সমস্ত স্বতন্ত্র মান থাকা অসম্ভব৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• ret:=0

• সাজান অ্যারে এ

• আগে কোন মান বিবেচনা করা হয় তা ট্র্যাক রাখতে ভিজিটড নামে একটি সেট তৈরি করুন

• আমি রেঞ্জ 1 থেকে অ্যারের আকার A – 1

  এর জন্য

  • যদি A[i]

• রিটার্ন রিটার্ন।

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minIncrementForUnique(vector<int>& A) {
      int ret = 0;
      sort(A.begin(), A.end());
      set <int> visited;
      for(int i = 1; i < A.size(); i++){
         if(A[i] <= A[i - 1]){
            ret+= (A[i - 1] + 1) - A[i];
            A[i] = A[i - 1] + 1;
         }
      }
      return ret;
   }
};
main(){
   vector<int> v1 = {3,2,1,2,1,7};
   Solution ob;
   cout << (ob.minIncrementForUnique(v1));
}

ইনপুট

[3,2,1,2,1,7]

আউটপুট

6