ゼロから始めるLeetCode Day8「2595. Number of Even and Odd Bits」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインでだそうです。

その対策としてLeetCodeなるサイトで対策を行うようです。

※LeetCodeとは
本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトです。

せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていきます。

LeetCode

未経験のエンジニアなので、基本的に簡単なもの（easyでacceptanceが高い順）から解いていきます。

問題

2595. Number of Even and Odd Bits

正の整数 n が与えられたとき、その二進数表現において、値が 1 であるビットの位置（インデックス）が偶数であるものの個数 (even) と、奇数であるものの個数 (odd) を数え上げ、それらを要素とする配列 [even, odd] を返すという問題。

Example 1:
Input: n = 50
Output: [1,2]
Explanation:
50の2進表現は110010である。
これはインデックス1、4、5に1を含む。

Example 2:
Input: n = 2
Output: [0,1]
Explanation:
2の2進表現は10である。
インデックス1にのみ1を含む。

Constraints:
1 <= n <= 1000

解法

class Solution:
    def evenOddBit(self, n: int) -> List[int]:
        binary_n = bin(n)[2:]
        even = 0
        odd = 0
        for i, bit in enumerate(reversed(binary_n)):
            if bit == '1':
                if i % 2 == 0:
                    even += 1
                else:
                    odd += 1
        return [even, odd]

binary_n = bin(n)[2:]
bin(50) は '0b110010' を返す。
これは50のバイナリ表現の前にプレフィックス '0b' が付いたものである。
[2:] スライスは、このプレフィックスを取り除き、純粋なバイナリ文字列110010を binary_n に格納する。

even = 0
偶数インデックスの数を追跡するためのカウンター。

odd = 0
奇数インデックスの数を追跡するためのカウンター。

for i, bit in enumerate(reversed(binary_n))
binary_nを反転させ、その各ビットをインデックスと共にループ処理する。

例

n = 50

50 = 110010

インデックス	ビット	even/odd カウンターの更新
0	0	変更なし
1	1	odd: 0 -> 1
2	0	変更なし
3	0	変更なし
4	1	even: 0 -> 1
5	1	odd: 1 -> 2

• 最終結果: [even, odd] は [1, 2]