Problem Description
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].
Key Insights
- The binary representation of a number can be accessed using bitwise operations.
- Even indices correspond to positions 0, 2, 4, etc., and odd indices correspond to positions 1, 3, 5, etc.
- We can use a loop to check each bit of the number and count the 1s at even and odd positions.
Space and Time Complexity
Time Complexity: O(log n) - the number of bits in the binary representation of n. Space Complexity: O(1) - only a fixed number of integer variables are used for counting.
Solution
To solve this problem, we will utilize bitwise operations to check each bit of the integer n. We will iterate through the bits of n and use bitwise AND to determine if a bit is set (1) at an even or odd index. We will maintain two counters: one for the even indices and one for the odd indices. At the end of the iteration, we will return the counts as an array.