Problem

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 that bits are indexed from right to left in the binary representation of a number.

Return the array [even, odd].

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Input: n = 50

Output: [1,2]

Explanation:

The binary representation of 50 is `110010`.

It contains 1 on indices 1, 4, and 5.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Input: n = 2

Output: [0,1]

Explanation:

The binary representation of 2 is `10`.

It contains 1 only on index 1.

Constraints

  • 1 <= n <= 1000

Solution

Method 1 – Bitwise Index Counting

Intuition

Iterate through the bits of n, counting 1s at even and odd indices (right to left, index 0 is least significant bit).

Approach

  1. For each bit in n, if the bit is 1, increment even or odd count depending on index parity.
  2. Return [even, odd].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    vector<int> evenOddBit(int n) {
        int even = 0, odd = 0, i = 0;
        while (n) {
            if (n & 1) (i%2 ? odd : even)++;
            n >>= 1; i++;
        }
        return {even, odd};
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func evenOddBit(n int) []int {
    even, odd, i := 0, 0, 0
    for n > 0 {
        if n&1 == 1 {
            if i%2 == 0 { even++ } else { odd++ }
        }
        n >>= 1; i++
    }
    return []int{even, odd}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int[] evenOddBit(int n) {
        int even = 0, odd = 0, i = 0;
        while (n > 0) {
            if ((n & 1) == 1) {
                if (i % 2 == 0) even++;
                else odd++;
            }
            n >>= 1; i++;
        }
        return new int[]{even, odd};
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun evenOddBit(n: Int): IntArray {
        var even = 0; var odd = 0; var i = 0; var nn = n
        while (nn > 0) {
            if (nn and 1 == 1) {
                if (i % 2 == 0) even++ else odd++
            }
            nn = nn shr 1; i++
        }
        return intArrayOf(even, odd)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def evenOddBit(self, n: int) -> list[int]:
        even, odd, i = 0, 0, 0
        while n:
            if n & 1:
                if i % 2 == 0:
                    even += 1
                else:
                    odd += 1
            n >>= 1; i += 1
        return [even, odd]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn even_odd_bit(n: i32) -> Vec<i32> {
        let (mut even, mut odd, mut i, mut nn) = (0, 0, 0, n);
        while nn > 0 {
            if nn & 1 == 1 {
                if i % 2 == 0 { even += 1; } else { odd += 1; }
            }
            nn >>= 1; i += 1;
        }
        vec![even, odd]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    evenOddBit(n: number): number[] {
        let even = 0, odd = 0, i = 0;
        while (n > 0) {
            if (n & 1) {
                if (i % 2 === 0) even++;
                else odd++;
            }
            n >>= 1; i++;
        }
        return [even, odd];
    }
}

Complexity

  • ⏰ Time complexity: O(log n).
  • 🧺 Space complexity: O(1).