Minimum Increment to Make Array Unique Solutions in C++

/// Source : https://leetcode.com/problems/minimum-increment-to-make-array-unique/
/// Author : liuyubobobo
/// Time   : 2018-11-24

#include <iostream>
#include <vector>

using namespace std;


/// Using sort and change the A array
/// Time Complexity: O(nlogn)
/// Space Complexity: O(1)
class Solution {
public:
    int minIncrementForUnique(vector<int>& A) {

        sort(A.begin(), A.end());
        int res = 0;
        for(int i = 1; i < A.size(); i ++)
            if(A[i] == A[i - 1]){
                res += (A[i - 1] + 1 - A[i]);
                A[i] = A[i - 1] + 1;
            }
        return res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/minimum-increment-to-make-array-unique/
/// Author : liuyubobobo
/// Time   : 2018-11-25

#include <iostream>
#include <vector>

using namespace std;


/// Using sort and don't change the A array
/// Time Complexity: O(nlogn)
/// Space Complexity: O(1)
class Solution {
public:
    int minIncrementForUnique(vector<int>& A) {

        if(A.size() == 0)
            return 0;

        sort(A.begin(), A.end());
        int res = 0, left = 0;
        for(int i = 1; i < A.size(); i ++)
            if(A[i] == A[i - 1]){
                left ++;
                res -= A[i];
            }
            else{
                int seg = min(left, A[i] - A[i - 1] - 1);
                res += (A[i - 1] + 1 + A[i - 1] + seg) * seg / 2;
                left -= seg;
            }

        if(left)
            res += (A.back() + 1 + A.back() + left) * left / 2;
        return res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/minimum-increment-to-make-array-unique/
/// Author : liuyubobobo
/// Time   : 2018-11-25

#include <iostream>
#include <vector>

using namespace std;


/// Using an array hashtable to record duplicate elements
/// Time Complexity: O(max number)
/// Space Complexity: O(max number)
class Solution {

private:
    const int MAX_NUM = 40000;

public:
    int minIncrementForUnique(vector<int>& A) {

        vector<int> freq(MAX_NUM + 1, 0);
        for(int a: A)
            freq[a] ++;

        int res = 0, left = 0;
        for(int i = 0; i <= MAX_NUM; i ++)
            if(freq[i] >= 2){
                res -= (freq[i] - 1) * i;
                left += freq[i] - 1;
            }
            else if(freq[i] == 0 && left){
                res += i;
                left --;
            }

        for(int i = 1; i <= left; i ++)
            res += (MAX_NUM + i);
        return res;
    }
};


int main() {

    return 0;
}