AtCoder ABC 068 B – Break Number Python解説

2021年11月21日

スポンサーリンク

Break Number

高橋君は 2 で割れる数が好きです。

正整数 N が与えられるので、1 以上 N 以下の整数のうち、最も 2 で割れる回数が多いものを求めてください。答えは必ず 1 つに定まります。

なお、2 で割っていき、何回あまりが出ずに割れるかを、2 で割れる回数と呼ぶことにします。

AtCoder株式会社 AtCoder Beginner Contest 068

愚直に解くとなると、与えられるNをひとつずつ2で割っていき、割れる回数を比べて、最も2で割れる回数が多い数字を出力すればよいです。

n = int(input())

ans = 0

for i in range(1, n + 1):
    cnt = 0
    index = i
    while True:
        if i % 2 == 0:
            cnt += 1
            i //= 2
        else:
            break
    if ans <= cnt:
        ans = cnt
        ans_index = index
        
print(ans_index)
    
        

ansには2で割れる回数の最大値を入れていきます。初めは0を初期値とし、割れる回数が更新されるたび、ansも更新していきます。

for文のcntはiが2で割れる回数をカウントしています。indexはどの数字が一番多く2で割れたかを管理しています。
こちらも2で割れる回数が更新されるたびに答えとなるans_indexを更新しています。

今回の問題は、与えられるNの最大値が100までだったので、全探索でも解答できましたが、もう少しシンプルに考えることもできます。

n = int(input())

i = 1

while True:
    if i * 2 <= n:
        i *= 2
    else:
        break
        
print(i)

上記のようにNを超えない範囲で、1に2を掛け続けた数値が一番2で割れる数になります。