- All Contests
- ProjectEuler+
- Project Euler #169: Exploring the number of different ways a number can be expressed as a sum of powers of 2.
- Discussions

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

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

vishnuamritpydah + 6 comments How would you do this in a language like C++, where there is no simple way to store an integer value of 10^27? Please advise.

rohit062 + 0 comments i suggest u to use biginteger in java

sashankaryal + 0 comments Make your own class

sashankaryal + 0 comments Or use std::string

Nassim_ + 0 comments use long int eg: long int N;

tsite + 0 comments use __int128

AlphaKun + 0 comments Or just use python

kalok87 + 2 comments My math sucks but I still figure out how to do this. Search Stern's Diatomics Series and try to understand it. For those friends who have timeout problem in python, try to build up a dictionary and extend it as far as you can(remember dic[2**N] = 1 for diatomic series) and add few more other elements like dic[3] = 2 or dic[5] = 3. Recursively use the function and remember to update your dic everytime(important, otherwise timeout). You should see that you program solve all cases in seconds.

Peddi_pankaj + 0 comments wow , i am amazed! . how did you know that it is Stern's Diatomics Series ? i am curious to know

sigmapie8 + 0 comments That really helped!

sandeepsmishra + 3 comments I was wondering should the

fn(10) be 12 like below

I dont understand what I am doing wrong here

soumabratabhatt1 + 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

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

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

15E125 + 1 comment i am not getting answerdef fn(n) : if (n == 0) or (n == 1): return n;

`elif (n % 2 == 0): #even return fn(n / 2); elif (n % 2 == 1): #odd return fn((n-1) / 2) + fn((n+1) / 2); return -1`

num = int(input()) print(int(fn(num+1)))

pyhejhu + 0 comments f(4)=3 (4,2+2,1+1+2) but f(2)=2 (2,1+1) so f(4)!=f(2)

nejihyuga + 0 comments use string

ripkinurulpauji1 + 0 comments bang tolong teransper saya udang bisa engga ? saya butuh uang 200rbu bang ??? :(())

Marco_L_T + 1 comment Having solved the problem recursively,but on my first attempt,my program got Terminated Due to Timeout because I don't record the result using map in C++. After recording the result of each number visited,it got accepted. Could anyone prove why just recording the result can make the time complexity right?

kilicars + 0 comments I understand that first you solved by only recursion and then added memoization to your solution. When memoization is used the recorded values are not calculated again and again as in pure recursive solution so it is faster.

Still I am not sure if you really asked this or probably you figured it out later..

Sort 28 Discussions, By:

Please Login in order to post a comment