Project Euler #169: Exploring the number of different ways a number can be expressed as a sum of powers of 2.

  • + 0 comments
    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