Find the maximum number of elements in subset

Array Hash Table Enumeration

26.8% acceptance

Feb 25, 2026

217

You are given an array of positive integers nums. You need to select a subset of nums which satisfies the following condition: You can place the selected elements in a 0-indexed array such that it follows the pattern: [x, x2, x4, ..., xk/2, xk, xk/2, ..., x4, x2, x] (Note that k can be be any non-negative power of 2). For example, [2, 4, 16, 4, 2] and [3, 9, 3] follow the pattern while [2, 4, 8, 4, 2] does not. Return the maximum number of elements in a subset that satisfies these conditions.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_length(nums: Vec<i32>) -> i32 {
    use std::collections::HashMap;
    let mut cnt: HashMap<i64, i64> = HashMap::new();
    for &n in &nums { *cnt.entry(n as i64).or_insert(0) += 1; }
    let mut ans = 1i32;
    for (&x, &c) in &cnt {
      if c == 0 { continue; }
      if x == 1 {
        let len = if c % 2 == 1 { c } else { c - 1 };
        ans = ans.max(len as i32);
        continue;
      }
      // Pattern: [x, x^2, x^4, ..., x^k, ..., x^4, x^2, x]
      // Length 1: just x (requires cnt[x] >= 1)
      let mut valid_len = 1i64;
      let mut cur = x;
      loop {
        let c_cur = *cnt.get(&cur).unwrap_or(&0);
        if c_cur < 2 { break; }
        if cur > 31623 { break; } // cur^2 would overflow
        let next = cur * cur;
        let c_next = *cnt.get(&next).unwrap_or(&0);
        if c_next < 1 { break; }
        valid_len += 2;
        cur = next;
      }
      ans = ans.max(valid_len as i32);
    }
    ans
  }
}