Welcome to Subscribe On Youtube
2595. Number of Even and Odd Bits
Description
You are given a positive integer n.
Let even denote the number of even indices in the binary representation of n (0-indexed) with value 1.
Let odd denote the number of odd indices in the binary representation of n (0-indexed) with value 1.
Return an integer array answer where answer = [even, odd].
Example 1:
Input: n = 17 Output: [2,0] Explanation: The binary representation of 17 is 10001. It contains 1 on the 0th and 4th indices. There are 2 even and 0 odd indices.
Example 2:
Input: n = 2 Output: [0,1] Explanation: The binary representation of 2 is 10. It contains 1 on the 1st index. There are 0 even and 1 odd indices.
Constraints:
1 <= n <= 1000
Solutions
Solution 1: Enumerate
According to the problem description, enumerate the binary representation of $n$ from the low bit to the high bit. If the bit is $1$, add $1$ to the corresponding counter according to whether the index of the bit is odd or even.
The time complexity is $O(\log n)$ and the space complexity is $O(1)$. Where $n$ is the given integer.
-
class Solution { public int[] evenOddBit(int n) { int[] ans = new int[2]; for (int i = 0; n > 0; n >>= 1, i ^= 1) { ans[i] += n & 1; } return ans; } } -
class Solution { public: vector<int> evenOddBit(int n) { vector<int> ans(2); for (int i = 0; n > 0; n >>= 1, i ^= 1) { ans[i] += n & 1; } return ans; } }; -
class Solution: def evenOddBit(self, n: int) -> List[int]: ans = [0, 0] i = 0 while n: ans[i] += n & 1 i ^= 1 n >>= 1 return ans -
func evenOddBit(n int) []int { ans := make([]int, 2) for i := 0; n != 0; n, i = n>>1, i^1 { ans[i] += n & 1 } return ans } -
function evenOddBit(n: number): number[] { const ans = new Array(2).fill(0); for (let i = 0; n > 0; n >>= 1, i ^= 1) { ans[i] += n & 1; } return ans; } -
impl Solution { pub fn even_odd_bit(mut n: i32) -> Vec<i32> { let mut ans = vec![0; 2]; let mut i = 0; while n != 0 { ans[i] += n & 1; n >>= 1; i ^= 1; } ans } }