Partitions into Powers of Two
National Olympiad — Municipal round (2016 season)
Submission name: sum.cpp
Problem summary
Count unordered representations of N as a sum of powers of two, allowing repeated summands and including 2^0.
Input
One integer N.
Output
The exact number of representations.
Constraints
1 ≤ N ≤ 3000.
Worked example
An independently prepared example for this explanation.
Input
6
Output
6
Solution analysis
- Treat each power of two not exceeding N as an unlimited coin denomination. Let ways[s] count representations of s using the denominations already processed.
- Initially ways[0]=1 for the empty sum. For each denomination p, scan sums s upward from p and add ways[s−p] to ways[s]. Upward order permits another copy of p; the outer denomination loop prevents counting different orders separately.
- For 6 the six partitions are 4+2, 4+1+1, 2+2+2, 2+2+1+1, 2+1+1+1+1, and six ones. At N=3000 the result is 6084830616290, which fits signed 64-bit arithmetic.
Why it works
When processing p, every representation either uses no p and was counted previously, or has a final copy of p whose removal leaves a representation of s−p using denominations up to p. These cases are disjoint and exhaustive. Induction over denominations proves the count.
Complexity: O(N log N) time and O(N) space.
Watch out. Use long long. Reversing the sum loop would allow each denomination only once.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n;
cin>>n;
vector<long long>ways(n+1,0);
ways[0]=1;
for(int power=1;power<=n;power*=2){
// Ascending sums allow arbitrarily many copies of this power.
for(int sum=power;sum<=n;++sum){
ways[sum]+=ways[sum-power];
}
}
cout<<ways[n]<<'\n';
}