Consider the TestCase :
1
8796093022208
Required Output:
2
17592186044415 8796093022207
Your Ouput:
2
4095 2047
Spolier
Use Long Long int instead of Int
Spoiler
Handle this testcase
Input:
1
0
Output:
2
1 1
2 Likes
Recursion also works.Obviously time taken is more.
#include <bits/stdc++.h>
using namespace std;
vector<unsigned long long int> ans;
void func(unsigned long long int x)
{
unsigned long long int lgvalue,finalvalue;
if(x == 1)
{
ans.push_back(1);
return;
}
else if(x==0)
{
return;
}
lgvalue = (unsigned long long int)log2(x)+1;
finalvalue = (unsigned long long int)powl(2,lgvalue)-1;
ans.push_back(finalvalue);
return func(finalvalue-x);
}
void solve()
{
ans.clear();
unsigned long long int c;
cin>>c;
if(c == 0)
{cout<<2<<endl<<"1 1"<<endl;
return;}
func(c);
cout<<(unsigned long long int)ans.size()<<endl;
reverse(ans.begin(),ans.end());
for(int i =0;i<ans.size();i++ )
{
cout<<ans[i]<<" ";
}
cout<<endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
solve();
}
}
1 Like
I have a slightly different approach that may be more intuitive. My Code
Convert C to binary.
Eg: 25 = 11001
Now, since numbers in array can only have set bits in binary form,
Therefore, for 11001
Ans=
11111
00111
00001
Conclusion:
At positions with set bit, number of set bits in the final answers array is odd
Algorithm:
Iterate from left to right and create a non-decreasing array
In this case:
1 1 0 0 1 → 1 1 2 2 3
How? At places with set bits in C, number of set bits should be odd and at unset bits, it should be even.
Now, from 1 1 2 2 3, you can very easily generate the binary numbers that are part of the final array.
Eg:
After 11111, Remaining → 00112
After 00111, Remaining → 00001
After 00001, Remaining → 00000
Implementation suggestion:
Using bitset will make work with binary numbers much easier
4 Likes
One thing I noticed is, In Line 17, Newline is missing at the end.
Can someone tell me what is wrong with my code?
I have used long long int and also handled c==0.
Thank you so much
Thank You so much
Just typecast
using namespace std;
#define ll long long int
#define MOD 1000000007
#define fast \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL);
#define pb push_back
#define mp make_pair
#define fi first
#define se second
void solve()
{
ll c;
cin >> c;
if (c == 0)
{
cout << 2 << endl;
cout << "1 1" << endl;
return;
}
int a[60] = {0};
int i = 1;
while (c > 0)
{
a[60 - i] = c % 2;
c = c / 2;
i++;
}
int prev = 0;
vector<ll> ans;
for (int i = 0; i < 60; i++)
{
if (prev == 0)
{
if (a[i] == 1)
{
ans.pb((unsigned long long int)pow(2, (60 - i)) - 1);
prev = 1;
}
}
else
{
if (a[i] == 0)
{
ans.pb((unsigned long long int)pow(2, (60 - i)) - 1);
prev = 0;
}
}
}
cout << ans.size() << endl;
for (auto &x : ans)
cout << x << " ";
cout << endl;
}
int main()
{
fast;
int t;
//t=1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
1 Like
Thanks man!
apparently a long long took its toll… can someone explain how different 1ll<<n is to 1<<n . or give reference to any article
1 Like
Please tell what’s wrong with the code. It is only passing one of the three test cases.
My solution : CodeChef: Practical coding for everyone
Can you please post your code also, that will be a great help for me.
i didnt understand editorial can anyone explain why using this approach any proof?
It is there in the first line
Just typecast your value returned by pow
#include <bits/stdc++.h>
using namespace std;
string binary(long long n)
{
string s = "";
if (n == 0)
{
s += '0';
return s;
}
while (n > 0)
{
long long k = n % 2;
s += to_string(k);
n = n / 2;
// cout << k << s[i] << endl;
}
// s[i] = '\0';
// reverse(s.begin(), s.end());
return s;
}
int main()
{
int t;
cin >> t;
while (t--)
{
long long n;
cin >> n;
string str = binary(n);
// cout << str << endl;
vector<long long> v;
if (str.size() == 1 and str[0] == '0')
{
v.push_back(1);
v.push_back(1);
}
else
{
int f = 1;
for (int i = str.size() - 1; i >= 0; i--)
{
char k = f + '0';
if (str[i] == k)
{
long long y = (long long int)pow(2, i + 1) - 1;
v.push_back(y);
f = 1 - f;
}
}
}
cout << v.size() << endl;
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
}
return 0;
}
I have done exactly the same.
I got the approach but can someone please explain that how is the size of the array minimum using this algo?