PyPy3 solution:

from math import log

d = {}

def num_ways(N):
    if N in d:
        return d[N]
    if N <= 1:
        return 1
    if N & 1:
        return num_ways(N >> 1)
    d[N] = num_ways(N >> 1) + num_ways((N >> 1) - 1)
    return d[N]
        
n = int(input())


print(num_ways(n))

The recurrence comes from generating functionology. E.g. suppose N = 10. int(log(N, 2)) = 3. Thus, the generating function of this is (1 + x + x^2)(1 + x^2 + x^4)(1 + x^4 + x^8). In general, when int(log(N, 2)) = k, we have: Pk = (1 + x + x^2)...(1 + x^(2^k) + x^(2^(k + 1)) ).

The solution is the coefficient in front of x^N Now, to obtain the reccurence, consider the following two cases: 2N + 1 and 2N. coeff(Pk, 2N + 1) = coeff(x * P_{k - 1}(x^2), 2N + 1) = coeff(P_{k - 1}, N) coeff(Pk, 2N) = coeff((1 + x^2)P_{k - 1}(x^2), 2N) = coeff(P_{k - 1}, N - 1) + coeff(P_{k - 1}, N)

It follows that f(2N + 1) = f(N) and f(2N) = f(N - 1) + f(N).

Python: just figure out // is floor division and / is float division. When n are very large, / will round your result and // will result in integer. Try the following code to see the difference print(10 ** 25 / 2, 10 ** 25 // 2)

n=int(input())
a=bin(n)[2:]
zeros=[]
count=0
for i in range(1,len(a)):
    if a[i]=='0':
        count+=1
    else:
        zeros.append(count)
        count=0
if a[len(a)-1]=='0':
    zeros.append(count)
res=[zeros[0]+1]
s1=[0]
s2=[1]
for i in range(1,len(zeros)):
    s1.append(res[i-1]+s1[i-1])
    s2.append(s1[i-1]+s2[i-1])
    res.append((s1[i]+s2[i])*zeros[i])
if n==0:
    print(1)
else:
    print(sum(res))

This solutions works

Can be solved more efficiently by dynamic programming. https://www.geeksforgeeks.org/perfect-sum-problem-print-subsets-given-sum/

public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */

    Scanner s = new Scanner(System.in);

    int n=s.nextInt();

    int l=0,x=0;

    ArrayList<Integer> al = new ArrayList();

    while(x<n){
        x = 1 << l;
        al.add(x);
    }

    int[] count = new int[n+1];

    count[0]=1;

    for(int i=1;i<n+1;i++){
        for(int j=0;j<al.size();j++){
            if(i>=al.get(j))
                count[i]+=count[i-al.get(j)];
        }
    }
    int k=count[n];
    System.out.println(k);
}

what is the problem..showing:unsafe operations