find-array-given-subset-sums.cpp

// Time:  O(n * 2^n), len(sums) = 2^n
// Space: O(1)

// [proof]
// - let d = sorted_sums[0]-sorted_sums[1] and d != -d (d = 0 is trival), where one of +d/-d is the smallest positive or largest negative number of the original solution of [S1, ..., S(2^n)]
// - given Sp-d = 0 for some p in [1, 2^n] and Sq-(-d) = 0 for some q in [1, 2^n]
//   assume d is a number of the original solution of [S1, ..., S(2^n)] (the proof where -d is a number of the original solution is vice versa)
//   let Sq = x1+...+xi where 1 <= i <= n-1
//   let [d]+[x1, ..., xi]+[x(i+1), ..., x(n-1)] be the original solution
//   => new_sums([S1, ..., S(2^n)], d)
//      = subset_sums([x1, ..., xi]+[x(i+1), ..., x(n-1)])
//   if we choose -d as a number of a solution of [S1, ..., S(2^n)]
//   => new_sums([S1, ..., S(2^n)], -d)
//      = new_sums([S1, ..., S(2^n)], -(x1+...+xi))
//      = subset_sums([(-x1), ..., (-xi)]+[x(i+1), ..., x(n-1)])
//      => [-d]+[(-x1), ..., (-xi)]+[x(i+1), ..., x(n-1)] is also a solution
//
// [conclusion]
// - if new_sums with +d/-d (including d = 0) both contain zero, we can choose either one
// - if only one of new_sums with +d/-d contains zero, we can only choose the one with zero since subset_sums must contain zero

// optimized from solution4 (not using unordered_map), runtime: 188 ms
class Solution {
public:
    vector<int> recoverArray(int n, vector<int>& sums) {
        sort(begin(sums), end(sums));  // Time: O(2^n * log(2^n)) = O(n * 2^n)
        int shift = 0, l = size(sums);
        vector<int> result;
        for (; n--; l /= 2) {  // log(2^n) times, each time costs O(2^(n-len(result))), Total Time: O(2^n)
            const int new_shift = sums[0] - sums[1];
            assert(new_shift <= 0);
            bool has_zero = false;
            for (int i = 0, j = 0, k = 0; i < l; ++i) {
                if (k < j && sums[k] == sums[i]) {  // skip shifted one
                    ++k;
                } else {
                    if (shift == sums[i] - new_shift) {
                        has_zero = true;
                    }
                    sums[j++] = sums[i] - new_shift;
                }
            }
            if (has_zero) {  // contain 0, choose this side
                result.emplace_back(new_shift);
            } else {  // contain no 0, choose another side and shift 0 offset
                result.emplace_back(-new_shift);
                shift -= new_shift;
            }
        }
        return result;
    }
};

// Time:  O(2^n + n * r), len(sums) = 2^n
//                      , r = max(sums)-min(sums)
// Space: O(2^n + r)
// optimized from solution4 (not using unordered_map), runtime: 148 ms
class Solution2 {
public:
    vector<int> recoverArray(int n, vector<int>& sums) {
        const int min_sum = *min_element(cbegin(sums), cend(sums));
        const int max_sum = *max_element(cbegin(sums), cend(sums));
        vector<int> dp(max_sum - min_sum + 1);
        for (const auto& sum : sums) {
            ++dp[sum - min_sum];
        }
        vector<int> sorted_sums;
        for (int x = min_sum; x <= max_sum; ++x) {
            if (dp[x - min_sum]) {
                sorted_sums.emplace_back(x);
            }
        }
        int shift = 0;
        vector<int> result;
        while (n--) { // log(2^n) times, each time costs O(2^(n-len(result)))+O(r), Total Time: O(2^n + n * r)
            vector<int> new_dp(max_sum - min_sum + 1);
            vector<int> new_sorted_sums;
            const int new_shift = (dp[sorted_sums[0] - min_sum] == 1) ? sorted_sums[0] - sorted_sums[1] : 0;
            assert(new_shift <= 0);
            for (const auto& x : sorted_sums) {
                if (!dp[x - min_sum]) {
                    continue;
                }
                dp[(x - new_shift) - min_sum] -= new_shift ? dp[x - min_sum] : dp[x - min_sum] / 2;
                new_dp[(x - new_shift) - min_sum] = dp[x - min_sum];
                new_sorted_sums.emplace_back(x - new_shift);
            }
            dp = move(new_dp);
            sorted_sums = move(new_sorted_sums);
            if (dp[shift - min_sum]) {  // contain 0, choose this side
                result.emplace_back(new_shift);
            } else {  // contain no 0, choose another side and shift 0 offset
                result.emplace_back(-new_shift);
                shift -= new_shift;
            }
        }
        return result;
    }
};

// Time:  O(n * 2^n), len(sums) = 2^n
// Space: O(2^n)
// optimized from solution4, runtime: 344 ms
class Solution3 {
public:
    vector<int> recoverArray(int n, vector<int>& sums) {
        unordered_map<int, int> dp;
        for (const auto& sum : sums) {
            ++dp[sum];
        }
        vector<int> sorted_sums;
        for (const auto& [k, _] : dp) {
            sorted_sums.emplace_back(k);
        }
        sort(begin(sorted_sums), end(sorted_sums));  // Time: O(2^n * log(2^n)) = O(n * 2^n)
        int shift = 0;
        uint32_t total = 0;
        for (const auto& [k, v] : dp) {
            total |= v;
        }
        const uint32_t basis = total & -total;  // find rightmost bit 1
        if (basis > 1) {
            for (auto& [_, v] : dp) {
                v /= basis;
            }
        }
        vector<int> result(bit_length(basis) - 1);
        n -= bit_length(basis) - 1;
        while (n--) {  // log(2^n) times, each time costs O(2^(n-len(result))), Total Time: O(2^n)
            unordered_map<int, int> new_dp;
            vector<int> new_sorted_sums;
            const int new_shift = (dp[sorted_sums[0]] == 1) ? sorted_sums[0] - sorted_sums[1] : 0;
            assert(new_shift <= 0);
            for (const auto& x : sorted_sums) {
                if (!dp[x]) {
                    continue;
                }
                dp[x - new_shift] -= new_shift ? dp[x] : dp[x] / 2;
                new_dp[x - new_shift] = dp[x];
                new_sorted_sums.emplace_back(x - new_shift);
            }
            dp = move(new_dp);
            sorted_sums = move(new_sorted_sums);
            if (dp.count(shift)) {  // contain 0, choose this side
                result.emplace_back(new_shift);
            } else {  // contain no 0, choose another side and shift 0 offset
                result.emplace_back(-new_shift);
                shift -= new_shift;
            }
        }
        return result;
    }

private:
    int bit_length(int x) {
        return x != 0 ? 32 - __builtin_clz(x) : 1;
    }
};

// Time:  O(n * 2^n), len(sums) = 2^n
// Space: O(2^n)
// runtime: 344 ms
class Solution4 {
public:
    vector<int> recoverArray(int n, vector<int>& sums) {
        unordered_map<int, int> dp;
        for (const auto& sum : sums) {
            ++dp[sum];
        }
        vector<int> sorted_sums;
        for (const auto& [k, _] : dp) {
            sorted_sums.emplace_back(k);
        }
        sort(begin(sorted_sums), end(sorted_sums));  // Time: O(2^n * log(2^n)) = O(n * 2^n)
        int shift = 0;
        vector<int> result;
        while (n--) {  // log(2^n) times, each time costs O(2^(n-len(result))), Total Time: O(2^n)
            unordered_map<int, int> new_dp;
            vector<int> new_sorted_sums;
            const int new_shift = (dp[sorted_sums[0]] == 1) ? sorted_sums[0] - sorted_sums[1] : 0;
            assert(new_shift <= 0);
            for (const auto& x : sorted_sums) {
                if (!dp[x]) {
                    continue;
                }
                dp[x - new_shift] -= new_shift ? dp[x] : dp[x] / 2;
                new_dp[x - new_shift] = dp[x];
                new_sorted_sums.emplace_back(x - new_shift);
            }
            dp = move(new_dp);
            sorted_sums = move(new_sorted_sums);
            if (dp.count(shift)) {  // contain 0, choose this side
                result.emplace_back(new_shift);
            } else {  // contain no 0, choose another side and shift 0 offset
                result.emplace_back(-new_shift);
                shift -= new_shift;
            }
        }
        return result;
    }
};