Number of Even and Odd Bits - Practice Coding Problems

Number of Even and Odd Bits - Problem

Bit Manipulation Easy

You are given a positive integer n.

Let even denote the number of even indices in the binary representation of n with value 1.

Let odd denote the number of odd indices in the binary representation of n with value 1.

Note: Bits are indexed from right to left in the binary representation of a number (0-indexed).

Return the array [even, odd].

Input & Output

Example 1 — Basic Case

$ Input: n = 17

› Output: [2,0]

💡 Note: 17 in binary is 10001. Even indices (0,2,4): bits are 1,0,1 → count = 2. Odd indices (1,3): bits are 0,0 → count = 0.

Example 2 — Mixed Positions

$ Input: n = 2

› Output: [0,1]

💡 Note: 2 in binary is 10. Even indices (0): bit is 0 → count = 0. Odd indices (1): bit is 1 → count = 1.

Example 3 — Larger Number

$ Input: n = 50

› Output: [1,2]

💡 Note: 50 in binary is 110010. Even indices (0,2,4): bits are 0,0,1 → count = 1. Odd indices (1,3,5): bits are 1,0,1 → count = 2.

Constraints

1 ≤ n ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Integer n = 17

Binary Conversion

Convert to binary: 10001, index positions 0,1,2,3,4 from right

Count by Parity

Even positions (0,2,4): 2 ones, Odd positions (1,3): 0 ones

Key Takeaway

🎯 Key Insight: Use bit operations to check each position while tracking even/odd parity for optimal O(1) space solution

Asked in

M Microsoft 15 a Amazon 12

The key insight is to process each bit position while tracking whether the position index is even or odd. The optimal bit manipulation approach uses bitwise operations to check each bit directly without string conversion. Time: O(log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Bit Operations	O(log n)	O(1)	Use bit shifting and masking to check each bit position directly
Binary String Conversion	O(log n)	O(log n)	Convert number to binary string and iterate through positions

Bit Operations — Algorithm Steps

Initialize position index and counters
While number > 0, check least significant bit
If bit is 1, increment appropriate counter based on position parity
Right shift number and increment position

Visualization

Tap to expand

Step-by-Step Walkthrough

Check LSB

Use n & 1 to check if least significant bit is 1

Count by Position

Increment even/odd counter based on current position

Shift & Continue

Right shift n and increment position until n becomes 0

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

void solution(int n, int* result) {
    int evenCount = 0;
    int oddCount = 0;
    int position = 0;
    
    while (n > 0) {
        if (n & 1) { // Check if least significant bit is 1
            if (position % 2 == 0) { // Even position
                evenCount++;
            } else { // Odd position
                oddCount++;
            }
        }
        
        n >>= 1; // Right shift to check next bit
        position++;
    }
    
    result[0] = evenCount;
    result[1] = oddCount;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int result[2];
    solution(n, result);
    
    printf("[%d,%d]\n", result[0], result[1]);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Process each bit position, total log n bits in the number

⚡ Linearithmic

Space Complexity

O(1)

Only use constant extra variables for counters and position tracking

✓ Linear Space

12.5K Views

Medium Frequency

~8 min Avg. Time

428 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bit Operations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler