0891-0900

891. Sum of Subsequence Widths $\star\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  int sumSubseqWidths(vector<int>& A) {
    const int n = A.size();
    const int kMod = 1e9 + 7;

    int ans = 0;
    long exp = 1;

    sort(A.begin(), A.end());

    for (int i = 0; i < n; ++i, exp = exp * 2 % kMod)
      ans = (ans + A[i] * exp - A[n - i - 1] * exp) % kMod;

    return ans;
  }
};

892. Surface Area of 3D Shapes $\star$

893. Groups of Special-Equivalent Strings $\star$

894. All Possible Full Binary Trees $\star\star$

895. Maximum Frequency Stack $\star\star\star$

896. Monotonic Array $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  bool isMonotonic(vector<int>& A) {
    bool increasing = true;
    bool decreasing = true;

    for (int i = 1; i < A.size(); ++i) {
      increasing &= A[i - 1] <= A[i];
      decreasing &= A[i - 1] >= A[i];
    }

    return increasing || decreasing;
  }
};

897. Increasing Order Search Tree $\star$

898. Bitwise ORs of Subarrays $\star\star$

899. Orderly Queue $\star\star\star$

900. RLE Iterator $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class RLEIterator {
 public:
  RLEIterator(vector<int>& A) { this->A = A; }

  int next(int n) {
    while (index < A.size() && A[index] < n) {
      n -= A[index];
      index += 2;
    }

    if (index == A.size()) return -1;

    A[index] -= n;

    return A[index + 1];
  }

 private:
  int index = 0;
  vector<int> A;
};