2595. Number of Even and Odd Bits

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

https://leetcode.cn/problems/number-of-even-and-odd-bits/

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

Test Cases

1
2

class Solution:
    def evenOddBit(self, n: int) -> List[int]:

1
2
3
4
5
6
7
8
9
10
11
12

import pytest

from solution import Solution


@pytest.mark.parametrize('n, expected', [
    (50, [1,2]),
    (2, [0,1]),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, n, expected):
    assert sol.evenOddBit(n) == expected

Thoughts

直接遍历 n 的每个二进制位。时间复杂度 O(log n)，空间复杂度 O(1)。

Code

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def evenOddBit(self, n: int) -> list[int]:
        counts = [0, 0]
        idx = 0
        while n > 0:
            if n & 1:
                counts[idx] += 1
            n >>= 1
            idx = 1 - idx

        return counts

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章