Number of Even and Odd Bits solution and explanation
Google
9 more videos on this problem
2595. Number of Even and Odd Bits | Weekly Contest 337 | LeetCode 2595Bro Coders · 3:29 · 960 views
2595. Number of Even and Odd Bits - JAVA (Weekly Contest 337)Sourin Majumdar · 4:27 · 547 views
Number of Even and Odd Bits | #6319 || Leetcode | Weekly contest 337 || EnglishVishwas aithal · 6:36 · 390 views
Number of Even and Odd Bits| Leetcode 2595 | BitWise | C++ | Weekly 337Tech Courses · 5:15 · 340 views
Leetcode 2595: Number of Even and Odd BitsAlgorithms Casts · 7:40 · 319 views
2595. Number of Even and Odd Bits (Leetcode Easy)Programming Live with Larry · 6:27 · 256 views
Leetcode Weekly contest 337 - Easy - Number of Even and Odd BitsPrakhar Agrawal · 2:50 · 194 views
Number of Even and Odd Bits || LeetCode Weekly Contest 337 || Solution || AcceptedHaribol · 0:10 · 134 views
2595. Number of Even and Odd Bits | BITS MANIPULATIONcode Explainer · 6:07 · 127 views
LeetCode 2595 : Number of Even and Odd Bits || EASY || JAVA || Detailed SolutionCodeGPT · 6:16 · 74 views
The 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].
Example 1:
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:
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
Approach overview
Problem Overview: Given an integer n, return an array where the first value is the number of set bits at even positions and the second value is the number of set bits at odd positions in the binary representation of n. Bit positions are counted from the least significant bit (LSB) starting at index 0.
Approach 1: Bit Manipulation (O(log n) time, O(1) space)
This approach processes the binary representation directly using bit operations. Repeatedly check the least significant bit with n & 1, which tells you whether the current bit is set. Track the current bit index and increment either the even or odd counter depending on its parity. After checking, right shift the number using n >>= 1 to move to the next bit.
The key insight is that every shift removes the processed bit while maintaining constant memory usage. The loop runs once for each bit in the number, which is at most log2(n). This method is efficient and avoids string conversion overhead. It’s a classic use of bit manipulation for inspecting binary structure directly.
Approach 2: String Manipulation (O(log n) time, O(log n) space)
Convert the integer into its binary string representation using functions like bin(n) in Python or Integer.toBinaryString() in Java. Iterate through the string from right to left so the least significant bit corresponds to index 0. For every character equal to '1', update either the even or odd counter depending on the index parity.
This approach is easier to visualize because you work directly with the binary digits as characters. However, it allocates additional memory for the string representation and performs extra conversions. Time complexity remains proportional to the number of bits, but space grows with the binary length. It combines string manipulation with basic binary analysis.
Recommended for interviews: The bit manipulation approach is the expected solution. It demonstrates comfort with binary operations such as & and bit shifting, both common in low-level algorithm questions. The string approach shows understanding of the problem but sacrifices constant space and efficiency. Interviewers typically prefer the direct bit-processing method because it reflects stronger control over binary representations.
Approach 1: Bit Manipulation
This approach involves bit manipulation to count the number of 1s at even and odd positions in the binary representation of the number. We can achieve this by using bit shifts and checking if a bit is set (1) or not.
def even_odd_bits(n):
even, odd = 0, 0
index = 0
while n > 0:
if n & 1:
if index % 2 == 0:
even += 1
else:
odd += 1
n >>= 1
index += 1
return [even, odd]
n = 50
result = even_odd_bits(n)
print(result)import java.util.Arrays;
public class EvenOddBits {
public static int[] evenOddBits(int n) {
int even = 0, odd = 0;
int index = 0;
while (n > 0) {
if ((n & 1) == 1) {
if (index % 2 == 0) {
even++;
} else {
odd++;
}
}
n >>= 1;
index++;
}
return new int[]{even, odd};
}
public static void main(String[] args) {
int n = 50;
int[] result = evenOddBits(n);
System.out.println(Arrays.toString(result));
}
}#include <iostream>
#include <vector>
std::vector<int> evenOddBits(int n) {
int even = 0, odd = 0;
int index = 0;
while (n > 0) {
if (n & 1) {
if (index % 2 == 0) {
++even;
} else {
++odd;
}
}
n >>= 1;
++index;
}
return {even, odd};
}
int main() {
int n = 50;
std::vector<int> result = evenOddBits(n);
std::cout << "[" << result[0] << ", " << result[1] << "]\n";
return 0;
}function evenOddBits(n) {
let even = 0, odd = 0;
let index = 0;
while (n > 0) {
if (n & 1) {
if (index % 2 === 0) {
even++;
} else {
odd++;
}
}
n >>= 1;
index++;
}
return [even, odd];
}
const n = 50;
const result = evenOddBits(n);
console.log(result);#include <stdio.h>
void even_odd_bits(int n, int* result) {
int even = 0, odd = 0;
int index = 0;
while (n > 0) {
if (n & 1) {
if (index % 2 == 0) {
even++;
} else {
odd++;
}
}
n >>= 1;
index++;
}
result[0] = even;
result[1] = odd;
}
int main() {
int n = 50;
int result[2];
even_odd_bits(n, result);
printf("[%d, %d]\n", result[0], result[1]);
return 0;
}using System;
class Program {
static int[] EvenOddBits(int n) {
int even = 0, odd = 0;
int index = 0;
while (n > 0) {
if ((n & 1) == 1) {
if (index % 2 == 0) {
even++;
} else {
odd++;
}
}
n >>= 1;
index++;
}
return new int[] { even, odd };
}
static void Main() {
int n = 50;
int[] result = EvenOddBits(n);
Console.WriteLine($"[{result[0]}, {result[1]}]");
}
}This Python code uses a similar logic to the above languages. It calculates the 1s at even and odd bit positions by iterating over the binary representation and applying bitwise operations.
Time Complexity: O(log n).
Space Complexity: O(1).
Approach 2: String Manipulation
This approach involves converting the number to its binary string representation and then iterating through the string characters to count 1s at even and odd indices based on the length of the string.
def even_odd_bits_string(n):
binary = bin(n)[2:]
even, odd = 0, 0
for i, bit in enumerate(reversed(binary)):
if bit == '1':
if i % 2 == 0:
even += 1
else:
odd += 1
return [even, odd]
n = 50
result = even_odd_bits_string(n)
print(result)import java.util.*;
public class EvenOddBitsString {
public static int[] evenOddBitsString(int n) {
String binary = Integer.toBinaryString(n);
int even = 0, odd = 0;
for (int i = 0; i < binary.length(); i++) {
if (binary.charAt(binary.length() - 1 - i) == '1') {
if (i % 2 == 0) {
even++;
} else {
odd++;
}
}
}
return new int[]{even, odd};
}
public static void main(String[] args) {
int n = 50;
int[] result = evenOddBitsString(n);
System.out.println(Arrays.toString(result));
}
}#include <iostream>
#include <string>
std::pair<int, int> evenOddBitsString(int n) {
std::string binary = std::bitset<32>(n).to_string();
int even = 0, odd = 0;
for (size_t i = 0; i < binary.size(); ++i) {
if (binary[binary.size() - 1 - i] == '1') {
if (i % 2 == 0) {
++even;
} else {
++odd;
}
}
}
return {even, odd};
}
int main() {
int n = 50;
auto result = evenOddBitsString(n);
std::cout << "[" << result.first << ", " << result.second << "]\n";
return 0;
}function evenOddBitsString(n) {
const binary = n.toString(2);
let even = 0, odd = 0;
for (let i = 0; i < binary.length; i++) {
if (binary[binary.length - 1 - i] === '1') {
if (i % 2 === 0) {
even++;
} else {
odd++;
}
}
}
return [even, odd];
}
const n = 50;
const result = evenOddBitsString(n);
console.log(result);#include <stdio.h>
#include <string.h>
void even_odd_bits_string(int n, int* result) {
char binary[32];
int index = 0, even = 0, odd = 0;
int length = 0;
while (n > 0) {
binary[length++] = (n & 1) + '0';
n >>= 1;
}
binary[length] = '\0';
for (int i = 0; i < length; i++) {
if (binary[i] == '1') {
if (i % 2 == 0) {
even++;
} else {
odd++;
}
}
}
result[0] = even;
result[1] = odd;
}
int main() {
int n = 50;
int result[2];
even_odd_bits_string(n, result);
printf("[%d, %d]\n", result[0], result[1]);
return 0;
}using System;
class Program {
static int[] EvenOddBitsString(int n) {
string binary = Convert.ToString(n, 2);
int even = 0, odd = 0;
for (int i = 0; i < binary.Length; i++) {
if (binary[binary.Length - 1 - i] == '1') {
if (i % 2 == 0) {
even++;
} else {
odd++;
}
}
}
return new int[] { even, odd };
}
static void Main() {
int n = 50;
int[] result = EvenOddBitsString(n);
Console.WriteLine($"[{result[0]}, {result[1]}]");
}
}This Python function converts the number to a binary string using Python's bin function, iterates over the string in reverse order, and counts the 1s.
Time Complexity: O(log n).
Space Complexity: O(log n).
Approach 3: 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.
function evenOddBit(n: number): number[] {
const ans = Array(2).fill(0);
for (let i = 0; n > 0; n >>= 1, i ^= 1) {
ans[i] += 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
}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
}
}Approach 4: Bit Manipulation
We can define a mask mask = 0x5555, which is represented in binary as 0101 0101 0101 0101_2. Then, performing a bitwise AND operation between n and mask will give us the bits at even indices in the binary representation of n. Performing a bitwise AND operation between n and the complement of mask will give us the bits at odd indices in the binary representation of n. We can count the number of 1s in these two results.
The time complexity is O(1), and the space complexity is O(1). Here, n is the given integer.
function evenOddBit(n: number): number[] {
const mask = 0x5555;
const even = bitCount(n & mask);
const odd = bitCount(n & ~mask);
return [even, odd];
}
function bitCount(i: number): number {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}func evenOddBit(n int) []int {
mask := 0x5555
even := bits.OnesCount32(uint32(n & mask))
odd := bits.OnesCount32(uint32(n & ^mask))
return []int{even, odd}
}impl Solution {
pub fn even_odd_bit(n: i32) -> Vec<i32> {
let mask: i32 = 0x5555;
let even = (n & mask).count_ones() as i32;
let odd = (n & !mask).count_ones() as i32;
vec![even, odd]
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Bit Manipulation | Time Complexity: O(log n). |
| String Manipulation | Time Complexity: O(log n). |
| Enumerate | – |
| Bit Manipulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bit Manipulation | O(log n) | O(1) | Best general solution; minimal memory and direct access to bits |
| String Manipulation | O(log n) | O(log n) | Useful for readability or when already working with binary strings |
Frequently asked questions
Is Number of Even and Odd Bits easy or hard?
Number of Even and Odd Bits is categorized as an Easy problem. It focuses on basic bit manipulation concepts such as checking set bits and shifting integers. Developers comfortable with binary operations typically solve it in a few lines of code.
Number of Even and Odd Bits Python/Java solution
In Python, repeatedly check n & 1 and shift with n >>= 1 while tracking the bit index. In Java, use the same logic with bitwise operators and integer variables. Both implementations run in O(log n) time and constant space since they process each bit once.
How to solve Number of Even and Odd Bits in O(log n)?
Use a loop that inspects the least significant bit with n & 1 and keeps track of the current bit index. If the bit is 1, increment the even or odd counter based on whether the index is even or odd. Shift the number right using n >>= 1 after each step. Continue until the number becomes zero.
What is the best approach for Number of Even and Odd Bits?
The bit manipulation approach is the most efficient. Iterate through the bits of the integer using n & 1 to check the current bit and right shift the number each step. Track the bit index to separate even and odd positions. This solution runs in O(log n) time and O(1) space.
Is Number of Even and Odd Bits asked at Google/Amazon/Meta?
This problem represents a typical bit manipulation exercise often used in technical interviews and coding assessments. Variations of bit counting and bit position analysis appear in interviews at companies like Google, Amazon, and Meta because they test understanding of binary operations and low-level reasoning.
What data structure is used in Number of Even and Odd Bits?
The problem primarily uses bit manipulation rather than traditional data structures. The algorithm operates directly on the integer’s binary representation using bitwise operations such as AND (&) and right shift (>>). The final result is stored in a simple array of two integers.
What is the time complexity of Number of Even and Odd Bits?
The optimal solution runs in O(log n) time because the algorithm processes each bit of the integer once. Since an integer with value n has roughly log2(n) bits, the loop executes that many iterations. Space complexity remains O(1) when using direct bit manipulation.