algoadvance

Leetcode 2595. Number of Even and Odd Bits

Problem Statement

You are given a positive integer n. Your task is to determine the number of bits set to 1 at even positions and the number of bits set to 1 at odd positions in the binary representation of n. Position indexes are 0-based from the least significant bit (rightmost bit).

Return an array where the first element is the number of 1 bits at even positions and the second element is the number of 1 bits at odd positions.

Clarifying Questions

  1. What is considered an even or odd position?
    • Even positions are indexed as 0, 2, 4, …, (0-based index).
    • Odd positions are indexed as 1, 3, 5, …, (0-based index).
  2. What is the expected input size?
    • The problem implies typical constraints for integers, so the upper limit is likely a 32-bit integer.
  3. Can we assume that the input is always valid?
    • Yes, the problem specifies that n is a positive integer.

Strategy

To solve this problem, we will:

  1. Initialize two counters that will count the number of 1 bits at even and odd positions respectively.
  2. Loop through each bit of n using bitwise operations:
    • Check if the current bit (either 0 or 1 position) is set.
    • Based on the position (even or odd), update the respective counter.
  3. Append the respective counts to the result array and return it.

Code

#include <vector>

std::vector<int> evenOddBitCounts(int n) {
    int evenCount = 0, oddCount = 0;
    int position = 0;
    
    while (n > 0) {
        if ((n & 1) == 1) { // Check if the least significant bit is set
            if (position % 2 == 0) {
                evenCount++;
            } else {
                oddCount++;
            }
        }
        n = n >> 1; // Right shift `n` to process the next bit
        position++;
    }
    
    return {evenCount, oddCount};
}

Time Complexity

The time complexity of this solution is O(log n) where n is the input number, because we are processing each bit of the number, and there are log(n) bits in the binary representation of n.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI