3020. Find the Maximum Number of Elements in Subset

MediumView on LeetCode

Array Hash Table Math

Time: O(n log max)

Space: O(n)

Problem Overview

Build a subset that looks like x, x², x⁴, … using copies from nums.

Intuition

Build a subset that looks like x, x², x⁴, … using copies from nums. Each intermediate value in the chain needs at least two copies (pair them); the terminal power needs only one. The value 1 is special because 1² = 1 — use every copy when the count is odd, otherwise drop one. Try every distinct starting value and take the maximum chain length.

Algorithm

1Frequency-map all values in nums; track maxNum.
2If 1 exists: ans = count[1] minus 1 when count[1] is even, else count[1].
3For each num ≠ 1: walk x = num, num², num⁴, … while x ≤ maxNum and count[x] ≥ 2, adding 2 to length each step.
4After the loop: add 1 if count[x] exists for the next power, else subtract 1.
5Return the maximum length over all starts.

Example Walkthrough

Input: nums with chain 2 → 4 → 16

1.Two 2s and two 4s give +2 each; one 16 adds +1 at the end.
2.Length 5 beats the all-1s chain if that is shorter.

Output: maximum subset size

Common Pitfalls

•Use long for x while squaring — int overflow before x > maxNum check.
•Handle 1 separately; the while-loop pairing rule does not apply to the 1-cycle.
•The final +1/−1 adjusts when the last pair has no singleton successor.

3020.cs

// Approach: Valid subset is a chain x, x², x⁴, … using multiset counts. For x > 1, take pairs
// (count ≥ 2) at each power until the chain breaks, then add one more if the next power exists.
// For x = 1, use all copies if count is odd, else count − 1. Track frequencies in a hash map.
// Time: O(n log max) Space: O(n)
public class Solution
{
    public int MaximumLength(int[] nums)
    {
        int maxNum = nums.Max();
        Dictionary<int, int> count = new Dictionary<int, int>();

        foreach (int num in nums)
            count[num] = count.GetValueOrDefault(num, 0) + 1;

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

        foreach (int num in nums)
        {
            if (num == 1)
                continue;
            int length = 0;
            long x = num;
            while (x <= maxNum && count.ContainsKey((int)x) && count[(int)x] >= 2)
            {
                length += 2;
                x *= x;
            }
            ans = Math.Max(ans, length + (count.ContainsKey((int)x) ? 1 : -1));
        }

        return ans;
    }
}

Was this solution helpful?