問題文

次のように定義される関数 f(n) があります。

f(n)=\begin{cases}0 & (n=0のとき)\\f(n-1)+1 & (n\geq 1 かつ\mathrm{popcount}(n)が奇数のとき)\\f(n-2)+1 & (n\geq 1 かつ\mathrm{popcount}(n)が偶数のとき)\end{cases}

\mathrm{popcount}(n) は n を 2 進法で表したときの 1 の個数を表します。例えば 13 は 2 進法で 1101 なので \mathrm{popcount}(13)=3 です。

正整数 N が与えられるので f(N) を求めてください。

制約

• 1 \le N \le 10^5
• N は整数

入力例1

3

出力例1

2

\mathrm{popcount}(3)=2、\mathrm{popcount}(1)=1 なので
f(3)=f(3-2)+1=(f(1-1)+1)+1=(0+1)+1=2 となります。

入力例2

67890

出力例2

45260

ヒント

テスト入出力

書いたプログラムが AC にならず、原因がどうしてもわからないときだけ見てください。

1

1

100000

66667

解答例

必ず自分で問題に挑戦してみてから見てください。

# 再帰上限の引き上げ
import sys
sys.setrecursionlimit(10**6)

def f(n):
    if n == 0:
        return 0
    if n.bit_count() % 2 == 1:
      return f(n-1) + 1
    else:
      return f(n-2) + 1

N = int(input())
print(f(N))