2834. Find the Minimum Possible Sum of a Beautiful Array

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    long long minimumPossibleSum(int n, int target) {
        int cur = 1;
        long long  ret = 1;
        unordered_set<int> unallowed ;
        unallowed.insert(target - cur);
        for(int i = 1;i<n;++i)
        {
            cur++;
            while(unallowed.count(cur)) cur++;
            ret+=cur;
            unallowed.insert(target - cur);
        }
        return ret;
    }
};

analysis

  • time complexity O(n)
  • space complexity O(n)