Question

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:
  def evenOddBit(self, n: int) -> List[int]:
    ans = [0, 0]
    i = 0
    while n:
      ans[i] += n & 1
      i ^= 1
      n >>= 1
    return ans

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;
  }
};

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
  }
}

Solution 2

class Solution:
  def evenOddBit(self, n: int) -> List[int]:
    mask = 0x5555
    even = (n & mask).bit_count()
    odd = (n & ~mask).bit_count()
    return [even, odd]

class Solution {
  public int[] evenOddBit(int n) {
    int mask = 0x5555;
    int even = Integer.bitCount(n & mask);
    int odd = Integer.bitCount(n & ~mask);
    return new int[] {even, odd};
  }
}

class Solution {
public:
  vector<int> evenOddBit(int n) {
    int mask = 0x5555;
    int even = __builtin_popcount(n & mask);
    int odd = __builtin_popcount(n & ~mask);
    return {even, odd};
  }
};

func evenOddBit(n int) []int {
  mask := 0x5555
  even := bits.OnesCount32(uint32(n & mask))
  odd := bits.OnesCount32(uint32(n & ^mask))
  return []int{even, odd}
}

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;
}

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]
  }
}