You are given an array of positive integers nums.
You need to select a subset of nums which satisfies the following condition:
[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.
Example 1:
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:
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 <= 1051 <= nums[i] <= 109class Solution {
public int maximumLength(int[] nums) {
Map<Integer, Integer> freq = new HashMap<>();
for (int i : nums)
freq.put(i, freq.getOrDefault(i, 0) + 1);
Map<Integer, Integer> series = new HashMap<>();
int maxm = 0, oneCt = freq.getOrDefault(1, 0);
if (oneCt > 0) {
maxm = (oneCt & 1) == 1 ? oneCt : oneCt - 1;
freq.remove(1);
}
for (Map.Entry<Integer, Integer> e : freq.entrySet())
maxm = Math.max(maxm, solve(e.getKey(), e.getValue(), freq, series, 1));
// System.out.println(series);
return maxm;
}
int solve(int key, int val, Map<Integer, Integer> freq, Map<Integer, Integer> series, int depth) {
if (series.containsKey(key))
return series.get(key);
if (val == 0)
return 0;
int sq = key * key;
if (val >= 2 && freq.containsKey(sq)) {
depth = solve(sq, freq.get(sq), freq, series, depth) + 2;
series.put(key, depth);
return depth;
}
// val == 1 or (val>=2 but square not present)
series.put(key, 1);
return 1;
}
}