Skip to content

3020. Find the Maximum Number of Elements in Subset 👍

  • 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
30
class Solution {
 public:
  int maximumLength(vector<int>& nums) {
    const int maxNum = ranges::max(nums);
    unordered_map<int, int> count;

    for (const int num : nums)
      ++count[num];

    int ans = count.contains(1) ? count[1] - (count[1] % 2 == 0) : 1;

    for (const int num : nums) {
      if (num == 1)
        continue;
      int length = 0;
      long x = num;
      while (x <= maxNum && count.contains(x) && count[x] >= 2) {
        length += 2;
        x *= x;
      }
      // x is now x^k, and the pattern is [x, ..., x^(k/2), x^(k/2), ..., x].
      // The goal is to determine if we can insert x^k in the middle of the
      // pattern to increase the length by 1. If not, we make x^(k/2) the middle
      // and decrease the length by 1.
      ans = max(ans, length + (count.contains(x) ? 1 : -1));
    }

    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
29
class Solution {
  public int maximumLength(int[] nums) {
    final int maxNum = Arrays.stream(nums).max().getAsInt();
    Map<Integer, Integer> count = new HashMap<>();

    for (final int num : nums)
      count.merge(num, 1, Integer::sum);

    int ans = count.containsKey(1) ? count.get(1) - (count.get(1) % 2 == 0 ? 1 : 0) : 1;

    for (final int num : nums) {
      if (num == 1)
        continue;
      int length = 0;
      long x = num;
      while (x <= maxNum && count.containsKey((int) x) && count.get((int) x) >= 2) {
        length += 2;
        x *= x;
      }
      // x is now x^k, and the pattern is [x, ..., x^(k/2), x^(k/2), ..., x].
      // The goal is to determine if we can insert x^k in the middle of the
      // pattern to increase the length by 1. If not, we make x^(k/2) the middle
      // and decrease the length by 1.
      ans = Math.max(ans, length + (count.containsKey((int) x) ? 1 : -1));
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def maximumLength(self, nums: list[int]) -> int:
    maxNum = max(nums)
    count = collections.Counter(nums)
    ans = count[1] - (count[1] % 2 == 0) if 1 in count else 1

    for num in nums:
      if num == 1:
        continue
      length = 0
      x = num
      while x <= maxNum and x in count and count[x] >= 2:
        length += 2
        x *= x
      # x is now x^k, and the pattern is [x, ..., x^(k/2), x^(k/2), ..., x].
      # The goal is to determine if we can insert x^k in the middle of the
      # pattern to increase the length by 1. If not, we make x^(k/2) the middle
      # and decrease the length by 1.
      ans = max(ans, length + (1 if x in count else -1))

    return ans