মান লেযিয়ে একটি পূর্ণসংখ্যা অ্যারে A দেওয়া আছে। এখানে একটি মুভ হল যেকোনো A[i] বেছে নিয়ে সেটি ১ দিয়ে ইনক্রিমেন্ট করা। A-এর সব মান ইউনিক করার জন্য ন্যূনতম মুভ সংখ্যা খুঁজে বের করতে হবে। ইনপুট [3,2,1,2,1,7] হলে আউটপুট ৬। ৬ মুভ পর অ্যারে হতে পারে [3,4,1,2,5,7], ৫ বা কম মুভে সব ডISTINCT মান পাওয়া সম্ভব নয়।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
ret := 0
অ্যারে A সর্ট করুন
visited নামে একটি সেট তৈরি করুন যাতে কোনো মান আগে বিবেচিত হয়েছে কিনা ট্র্যাক করা যায়
i = 1 থেকে A.size()-1 পর্যন্ত লুপ চালান
যদি A[i] <= A[i-1] হয়, ret := ret + (A[i-1] + 1) - A[i], এবং A[i] := A[i-1] + 1
ret রিটার্ন করুন
নিচের বাস্তবায়নটি দেখে আরও ভালো বুঝতে পারবেন -
উদাহরণ
#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
