मान लीजिए हमारे पास पूर्णांकों का एक ऐरे A है, यहां एक चाल में किसी भी A[i] को चुनकर उसे 1 से बढ़ाना शामिल है। हमें हर मान को A में यूनिक बनाने के लिए चालों की न्यूनतम संख्या खोजनी है।
उदाहरण के लिए, यदि इनपुट [3,2,1,2,1,7] है, तो आउटपुट 6 होगा, क्योंकि 6 चालों के बाद ऐरे [3,4,1,2,5,7] हो सकता है, यह दिखाया जा सकता है कि 5 या कम चालों में ऐरे के सभी मान विशिष्ट होना असंभव है।
समाधान दृष्टिकोण
ret := 0
ऐरे A को सॉर्ट करें
i को 1 से n-1 तक: यदि A[i] ≤ A[i-1], तो ret += (A[i-1] + 1) - A[i], और A[i] = A[i-1] + 1
ret लौटाएं
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minIncrementForUnique(vector<int>& A) {
int ret = 0;
sort(A.begin(), A.end());
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;
}
};
int main(){
vector<int> v1 = {3,2,1,2,1,7};
Solution ob;
cout << (ob.minIncrementForUnique(v1));
return 0;
}
इनपुट
[3,2,1,2,1,7]
आउटपुट
6