Sponsored
This approach involves sorting the array first, and then iterating through it to ensure each element is greater than the previous. By keeping track of the necessary increments for each duplicate, we can ensure that every element in the array becomes unique.
Time Complexity: O(N log N) due to sorting and O(N) for linear traversal, resulting in O(N log N) overall.
Space Complexity: O(1) since no auxiliary space is used beyond input manipulation.
1using System;
2
3class Solution {
4 public int MinIncrementForUnique(int[] nums) {
5 Array.Sort(nums);
6 int moves = 0, need = nums[0];
7 foreach (int num in nums) {
8 moves += Math.Max(0, need - num);
9 need = Math.Max(need, num) + 1;
10 }
11 return moves;
12 }
13
14 static void Main() {
15 var nums = new int[]{3, 2, 1, 2, 1, 7};
16 var sol = new Solution();
17 Console.WriteLine(sol.MinIncrementForUnique(nums));
18 }
19}This C# solution sorts the array and iterates through it to calculate the total moves required to ensure every number is unique. It keeps track of the next needed unique number during traversal.
Instead of sorting, this method uses an array to count occurrences of each integer and then processes the count. For duplicate values, increments are calculated to fill gaps until all numbers are unique.
Time Complexity: O(N + M) where M is the range of numbers, due to counting and traversal.
Space Complexity: O(M) where M is the maximum possible number in nums.
1#include <vector>
#include <cmath>
using namespace std;
int minIncrementForUnique(vector<int>& nums) {
int count[100000] = {0};
for (int num : nums) count[num]++;
int moves = 0, taken = 0;
for (int i = 0; i < 100000; ++i) {
if (count[i] > 1) {
taken += count[i] - 1;
moves -= i * (count[i] - 1);
} else if (taken > 0 && count[i] == 0) {
--taken;
moves += i;
}
}
return moves;
}
int main() {
vector<int> nums = {3, 2, 1, 2, 1, 7};
cout << minIncrementForUnique(nums) << endl;
return 0;
}In this C++ solution, a counting array is used to determine how many times each number appears. We then manage excess numbers by replacing them into the next open positions, using a variable to track these replacements effectively.