Problem

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 themaximum number of elements in a subset that satisfies these conditions.

Examples

Example 1

1
2
3

Input: nums = [5,4,1,2,2]
Output: 3
Explanation: We can select the subset {4,2,2}, which can be placed in the array as [2,4,2] which follows the pattern and 22 == 4. Hence the answer is 3.

Example 2

1
2
3

Input: nums = [1,3,2,4]
Output: 1
Explanation: We can select the subset {1}, which can be placed in the array as [1] which follows the pattern. Hence the answer is 1. Note that we could have also selected the subsets {2}, {3}, or {4}, there may be multiple subsets which provide the same answer.

Constraints

  • 2 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

Solution

Method 1 – Hash Map and Symmetric Expansion

Intuition

The pattern is a palindrome where the center is a power of 2, and the sequence expands symmetrically by multiplying/dividing by 2. For each number, try to expand outwards by multiplying/dividing by 2, using available counts in the array.

Approach

  1. Count the frequency of each number in nums.
  2. For each unique number, treat it as the center and try to expand outwards:
    • For each possible expansion, check if both x * 2^i and x / 2^i exist in the array (and are integers).
    • Use the minimum available count for symmetric pairs.
    • Track the maximum length found.
  3. Return the maximum length.

Code

 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

class Solution {
public:
    int maximumLength(vector<int>& nums) {
        unordered_map<int,int> cnt;
        for(int x:nums) cnt[x]++;
        int ans = 0;
        for(auto& [x, c]:cnt) {
            int len = 1, cur = x;
            int used = 1;
            while(cur%2==0 && cnt.count(cur/2)) {
                cur /= 2;
                used++;
            }
            len = used;
            cur = x;
            used = 1;
            while(cnt.count(cur*2)) {
                cur *= 2;
                used++;
            }
            len = max(len, used);
            ans = max(ans, len);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func maximumLength(nums []int) int {
    cnt := map[int]int{}
    for _, x := range nums { cnt[x]++ }
    ans := 0
    for x := range cnt {
        len1, cur := 1, x
        for cur%2==0 && cnt[cur/2]>0 {
            cur /= 2
            len1++
        }
        len2, cur := 1, x
        for cnt[cur*2]>0 {
            cur *= 2
            len2++
        }
        if len1 > ans { ans = len1 }
        if len2 > ans { ans = len2 }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int maximumLength(int[] nums) {
        Map<Integer,Integer> cnt = new HashMap<>();
        for(int x:nums) cnt.put(x, cnt.getOrDefault(x,0)+1);
        int ans = 0;
        for(int x:cnt.keySet()) {
            int len1=1, cur=x;
            while(cur%2==0 && cnt.containsKey(cur/2)) {
                cur/=2; len1++;
            }
            int len2=1; cur=x;
            while(cnt.containsKey(cur*2)) {
                cur*=2; len2++;
            }
            ans = Math.max(ans, Math.max(len1,len2));
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun maximumLength(nums: IntArray): Int {
        val cnt = nums.groupingBy { it }.eachCount()
        var ans = 0
        for (x in cnt.keys) {
            var len1 = 1; var cur = x
            while (cur%2==0 && cnt.containsKey(cur/2)) {
                cur /= 2; len1++
            }
            var len2 = 1; cur = x
            while (cnt.containsKey(cur*2)) {
                cur *= 2; len2++
            }
            ans = maxOf(ans, len1, len2)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def maximumLength(self, nums: list[int]) -> int:
        from collections import Counter
        cnt = Counter(nums)
        ans = 0
        for x in cnt:
            len1, cur = 1, x
            while cur%2==0 and cnt.get(cur//2,0)>0:
                cur //= 2
                len1 += 1
            len2, cur = 1, x
            while cnt.get(cur*2,0)>0:
                cur *= 2
                len2 += 1
            ans = max(ans, len1, len2)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

use std::collections::HashMap;
impl Solution {
    pub fn maximum_length(nums: Vec<i32>) -> i32 {
        let mut cnt = HashMap::new();
        for &x in &nums { *cnt.entry(x).or_insert(0) += 1; }
        let mut ans = 0;
        for &x in cnt.keys() {
            let mut len1 = 1; let mut cur = x;
            while cur%2==0 && cnt.contains_key(&(cur/2)) {
                cur /= 2; len1 += 1;
            }
            let mut len2 = 1; cur = x;
            while cnt.contains_key(&(cur*2)) {
                cur *= 2; len2 += 1;
            }
            ans = ans.max(len1).max(len2);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    maximumLength(nums: number[]): number {
        const cnt = new Map<number, number>();
        for(const x of nums) cnt.set(x, (cnt.get(x)||0)+1);
        let ans = 0;
        for(const x of cnt.keys()) {
            let len1=1, cur=x;
            while(cur%2===0 && cnt.has(cur/2)) {
                cur/=2; len1++;
            }
            let len2=1; cur=x;
            while(cnt.has(cur*2)) {
                cur*=2; len2++;
            }
            ans = Math.max(ans, len1, len2);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log M), where n is the length of nums and M is the maximum value in nums.
  • 🧺 Space complexity: O(n), for the frequency map.