Filter by Popcount Power of Two
In many performance-critical systems, understanding and leveraging the bitwise properties of data can lead to highly optimized algorithms. This problem focuses on a specific bitwise characteristic, the "popcount" (or Hamming weight), which is the count of set bits in a binary representation of a number. We're interested in identifying numbers whose popcount itself exhibits a particular property: being a power of two. This kind of filtering might be useful in scenarios like custom data indexing, error detection, or specialized data compression.
Implement a function filterByPopcountPowerOfTwo that takes an array of non-negative integers nums. Your task is to return a new array containing only those numbers from the input nums whose Hamming weight (the count of set bits in their binary representation) is itself a power of two.
nums: number[]
number[]
nums should result in an empty output array.nums are non-negative. 0 has a popcount of 0. Note that 0 is not considered a power of two when checking if a number is a power of two.Examples
Example 1
Input:
nums = [1, 2, 3, 4, 5, 6, 7]
Output:
[1,2,3,4,5,6]
Note:
1 (popcount 1, 1 is 2^0), 2 (popcount 1, 1 is 2^0), 3 (popcount 2, 2 is 2^1), 4 (popcount 1, 1 is 2^0), 5 (popcount 2, 2 is 2^1), 6 (popcount 2, 2 is 2^1) are included. 7 (popcount 3) is excluded as 3 is not a power of two.
Example 2
Input:
nums = [0, 8, 15, 16]
Output:
[8,15,16]
Note:
0 (popcount 0) is excluded as 0 is not considered a power of two. 8 (binary 1000) has popcount 1, and 1 is a power of two (2^0). 15 (binary 1111) has popcount 4, and 4 is a power of two (2^2). 16 (binary 10000) has popcount 1, and 1 is a power of two (2^0).
Example 3
Input:
nums = [1023, 1024, 2047, 2048]
Output:
[1024,2048]
Note:
1023 (binary 1111111111) has popcount 10, which is not a power of two. 1024 (binary 10000000000) has popcount 1, which is a power of two (2^0). 2047 (binary 11111111111) has popcount 11, which is not a power of two. 2048 (binary 100000000000) has popcount 1, which is a power of two (2^0).
Constraints
1 <= nums.length <= 10^50 <= nums[i] <= 2^31 - 1 (Numbers fit within a standard 32-bit unsigned integer)O(N * log(max_val)) where log(max_val) is effectively 32 (for a 32-bit integer), or O(N * C) where C is a constant (e.g., 32).O(1) beyond the space required for the output array.0, 1, and various powers of two, as well as numbers with many or few set bits.Loading editor...