Skip to content

1664. Ways to Make a Fair Array 👍

Approach 1: $O(n)$ space

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
 public:
  int waysToMakeFair(vector<int>& nums) {
    const int n = nums.size();
    int ans = 0;
    vector<int> even(n + 1);  // the sum of even-indexed nums[0..i)
    vector<int> odd(n + 1);   // the sum of odd-indexed nums[0..i)

    for (int i = 1; i <= n; ++i) {
      odd[i] = odd[i - 1];
      even[i] = even[i - 1];
      if (i % 2 == 0)
        even[i] += nums[i - 1];
      else
        odd[i] += nums[i - 1];
    }

    const int sum = even.back() + odd.back();

    for (int i = 0; i < n; ++i) {
      const int evenSum = even[i] + odd.back() - odd[i + 1];
      const int oddSum = sum - nums[i] - evenSum;
      if (evenSum == oddSum)
        ++ans;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
  public int waysToMakeFair(int[] nums) {
    final int n = nums.length;
    int ans = 0;
    int[] even = new int[n + 1]; // the sum of even-indexed nums[0..i)
    int[] odd = new int[n + 1];  // the sum of odd-indexed nums[0..i)

    for (int i = 1; i <= n; ++i) {
      odd[i] = odd[i - 1];
      even[i] = even[i - 1];
      if (i % 2 == 0)
        even[i] += nums[i - 1];
      else
        odd[i] += nums[i - 1];
    }

    final int sum = even[n] + odd[n];

    for (int i = 0; i < n; ++i) {
      final int evenSum = even[i] + odd[n] - odd[i + 1];
      final int oddSum = sum - nums[i] - evenSum;
      if (evenSum == oddSum)
        ++ans;
    }

    return ans;
  }
}

Approach 2: $O(1)$ space

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  int waysToMakeFair(vector<int>& nums) {
    const int n = nums.size();
    int ans = 0;
    // l[0] := the sum of even-indexed nums[0..i)
    // l[1] := the sum of odd-indexed nums[0..i)
    // r[0] := the sum of even-indexed nums[i + 1..n)
    // r[1] := the sum of odd-indexed nums[i + 1..n)
    vector<int> l(2);
    vector<int> r(2);

    for (int i = 0; i < n; ++i)
      r[i % 2] += nums[i];

    for (int i = 0; i < n; ++i) {
      r[i % 2] -= nums[i];
      if (l[0] + r[1] == l[1] + r[0])
        ++ans;
      l[i % 2] += nums[i];
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public int waysToMakeFair(int[] nums) {
    final int n = nums.length;
    int ans = 0;
    // l[0] := the sum of even-indexed nums[0..i)
    // l[1] := the sum of odd-indexed nums[0..i)
    // r[0] := the sum of even-indexed nums[i + 1..n)
    // r[1] := the sum of odd-indexed nums[i + 1..n)
    int[] l = new int[2];
    int[] r = new int[2];

    for (int i = 0; i < n; ++i)
      r[i % 2] += nums[i];

    for (int i = 0; i < n; ++i) {
      r[i % 2] -= nums[i];
      if (l[0] + r[1] == l[1] + r[0])
        ++ans;
      l[i % 2] += nums[i];
    }

    return ans;
  }
}