Problem
Contest
Author: Pranavram V
tester: Pranavram V
Editorialist: Pranavram V
Difficulty: Easy
PREREQUISITES: Basic math
Solution:
It can be easily seen that the subset can be generated by printing the ith element of the set S if the ith bit is set in the binary representation of n and not printing anything if the bit is not set.
Time Complexity : O(t*logn)
C++14 solution:
#include<bits/stdc++.h>
#define int long long int
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int poww(int n,int p)
{
int power=1;
for(int i=0;i<p;i++)
{
power=power*n;
}
return power;
}
int32_t main()
{
fast;
int t;
cin>>t;
while(t–)
{
int n,cnt=0,x;
cin>>n;
vector v;
while(n)
{
x=n&1;
if(x)
{
v.push_back(poww(3,cnt));
}
n=n>>1;
cnt++;
}
cout<<v.size()<<’\n’;
for(int i=0;i<v.size();i++)
{
cout<<v[i]<<" ";
}
cout<<’\n’;
}
}
Python3 solution:
t = int(input())
while t > 0:
n = int(input())
a = []
for i in range(0, 40):
if n >> i & 1:
a.append(3 ** i)
print(len(a))
print(*a)
t -= 1