PROBLEM LINK:
Author: Shriram Chandran
Editorialist: Shriram Chandran
DIFFICULTY:
Medium
PREREQUISITES:
Math, recursion.
PROBLEM:
Given a number N, find the number of numbers less than or equal to N such that it can be represented as a sum of distinct powers of 3.
There are various solutions to this question.
EXPLANATION 1:
First, let us make an observation on all 3-regular numbers: they all have only 0s and 1s in their ternary representation. This is because if there is any 2 in the ternary representation, you can not represent it using distinct powers of 3.
Thus, let us find the ternary representation of N, and assume it has d digits. We will now calculate the number of 3-regular numbers having at most d digits and less than N.
Note that all numbers with less than d digits will definitely be smaller than N. Thus for any i digit number, we fix the MSD as 1 and choose one of 2 options for other i-1 digits. So we add to our answer 2^{i-1} for all 1 \leq i \leq d.
For d digit numbers, this does not work. To calculate answer for d digit numbers, we use the following recursion:
- If d=1, the answer is just 1, since N=1 or N=2 and only 1 is 3-regular in these.
- Let d>1. We use the following idea: (i) if a particular digit is 0, we cannot make it 1 or 2 since the number will be greater than N. Thus, we will have to fix 0 when we move to the next digit (ii) if a particular digit is 1, we can fix this as 1 and move to the next digit, or we can fix this digit as 0 and choose any digit for the next positions. (iii) if a particular digit is 2, we can choose 0 or 1 for any digit that comes at or after this digit.
- Do not forget the corner conditions such as last digit or first digit (first digit can not be zero, since we are fixing number of digits and this will lead to repetitions).
Thus, we obtain the recursion f(n,d,i), where n is the number,d is the number of digits and i is the current digit.
ALTERNATIVE SOLUTION:
Binary search the k^{th} 3-regular number and check how it compares to N. We know that 1 \leq k \leq N.
ALTERNATIVE SOLUTION 2:
You can run a DP based on the recursion.
SOLUTION:
Setter's Solution based on recursion
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll calc(string s,int i)
{
if(s.size()==1)
return 1;
else if(i==s.size()-1)
{
if(s[i]=='0')
return 1;
else return 2;
}
else if(i==0)
{
if(s[i]=='2')
return pow(2,s.size()-1);
else return calc(s,i+1);
}
else
{
if(s[i]=='2')
return pow(2,s.size()-i);
else if(s[i]=='1')
return pow(2,s.size()-i-1)+calc(s,i+1);
else return calc(s,i+1);
}
}
void solve()
{
ll n;
cin>>n;
string s;
ll n1=n;
while(n1)
{
s=(char)(n1%3+48)+s;
n1/=3;
}
ll ans=0;
for(int i=1;i<s.size();i++)
ans+=pow(2,i-1);
ans+=calc(s,0);
cout<<ans<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}
