Frontend School

Filter by Popcount Power of Two

DSA
medium

Filter by Popcount Power of Two

Medium
Bit Manipulation
Arrays
Filtering

Overview

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.

What you need to do / Task

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.

Input & output

  • Input: nums: number[]
    • An array of non-negative integers.
  • Output: number[]
    • A new array containing only the filtered integers that satisfy the condition.

Clarifications

  • An empty input array nums should result in an empty output array.
  • The numbers in 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.
  • The order of elements in the output array should be the same as their relative order in the input array.

Examples

1

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.

2

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).

3

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

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 2^31 - 1 (Numbers fit within a standard 32-bit unsigned integer)
  • The solution should aim for optimal time complexity, ideally 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).
  • Auxiliary space complexity should be O(1) beyond the space required for the output array.

What interviewers evaluate

  • Correctness: The solution must accurately identify and filter numbers based on the specified bitwise criteria.
  • Efficiency: The implementation should leverage efficient bit manipulation techniques for both popcount calculation and power-of-two checks.
  • Edge Case Handling: Proper handling of numbers like 0, 1, and various powers of two, as well as numbers with many or few set bits.
  • Code Quality: Clarity, readability, and maintainability of the code, including appropriate variable naming and function structure.

Loading editor...