#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;
}
can anyone help me with my code ,
I found a pattern , and it works for each case , cant find anyone that fails .
Please help . Here is code #include <bits/stdc++.h>
using namespace std; #define ll long long
int main() {
// your code goes here
ll t;
cin>>t;
while(t–)
{
ll c;
cin>>c;
ll twos = 2;
ll temp = twos-1;
for _ in range(int(input())):
n = int(input())
if n==0:
ans += "1\n1 1\n"
continue
if (n+1)&n==0:
ans += str(1)+"\n" + str(n)+"\n"
continue
num = bin(n)[2:]
l = len(num)
res = []
cnt = 1
for i in range(len(num)):
if num[i]=="1" and (cnt)%2!=0:
res.append(int('1'*(l-i), 2))
cnt+=1
elif num[i]=="0" and cnt%2==0:
res.append(int('1'*(l-i), 2))
cnt+=1
elif num[i]=='0' and cnt%2!=0:
continue
elif num[i]=='1' and cnt%2==0:
continue
ans += str(len(res)) + "\n"
for i in res:
ans += str(i) + " "
ans += "\n"
print(ans)```
Let’s understand it with an example. But before going through the example, you should know this property of the Bitwise Exclusive-OR function.
Let A = [A_1,\ A_2,\ A_3,\ \dots,\ A_N]. Let X = A_1 \oplus A_2 \oplus A_3\oplus \dots\oplus A_N(\oplus\ \text{denotes bitwise EX-OR operator}).
i^{th} bit in X is set iff the number of elements (of A) having i^{th} bit set is Odd.
Now you know this property, we’ll move into an example.
Let \text{bin(C) = 1 1 0 1 0 0 0 1}. It is given that A_i = (2^x - 1)\ \forall\ i\in [1, N].
Moving from \text{MSB} to \text{LSB}, for now, let i = 0 denote position of \text{MSB} and i = K denote position of \text{LSB}:
i = 0:\text{bit}[\text{i}] = 1. So, we need an Odd number of elements having this bit set. To minimise the number of elements, the number of elements having this bit set shall be 1. Given that A_i = 2^x - 1. So we will choose A_1 = (11111111)_2 = 2^8 - 1 = (255)_{10}.
Why can’t we choose A_1 = (2^K - 1), \text{for some}\ K \ge 9?
If we pick K\ge9, we have to reset other higher order bits too → requires more elements. -\ (1)
i = 1:\ \text{bit[i] = 0}. So, we need odd number of elements having this bit set. Notice that A_1 = (2^8 - 1) already has this bit set and it is the only element so far. Since the requirement (Odd number of elements having this bit set) is already satisfied, we proceed for next bit.
i = 2:\ \text{bit[i] = 0}. So, we need Even number of elements having this bit set. Our sequence so far is [(11111111)_2] → there are odd number of elements having this bit set. We have to make it even. So, we add another element A_2 = (111111)_2 = (2^6 - 1) = (63)_{10}.
Now A = [(11111111)_2,\ (111111)_2] = [(255)_{10},\ (63)_{10}]
This process continues., and at the end the sequence A becomes A = [(11111111)_2,\ (111111)_2,\ (11111)_2,\ (1111)_2,\ (1)_2] = [(255)_{10},\ (63)_{10},\ (31)_{10},\ (15)_{10},\ (1)_{10}].
The only step you should bother about is marked as (1): Setting up bits unnecessarily will require additional elements to reset. So, to minimise the number of elements, we make use of the property of Bitwise Exclusive-OR \oplus operation: i^{th}\text{bit is set iff the number of elements having this bit set is Odd}.
At each step, we will greedily pick an Integer that minimises the additional elements required. The way we choose an element will impact the number of elements required in the next iteration of i.
You should also note that |A| will not exceed 60 and the input for |A| = \text{60} should be C = (101010\dots)_2,\ (|\text{bin}(c))| = 60.
My Solution using same approach
/*
* Author: Chitturi Sai Suman
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
void solve() {
ll N = 0;
cin >> N;
if(N == 0) {
cout << "2\n1 1\n";
return;
}
vector<ll> answer;
int c = 0;
for(int i = 61; i >= 0; i--) {
if(((N >> i) & 1) == 1) {
if(c % 2 == 0) {
answer.push_back((1LL << (i + 1)) - 1);
c++;
}
}
else {
if(c % 2 == 1) {
answer.push_back((1LL << (i + 1)) - 1);
c++;
}
}
}
cout << c << '\n';
for(auto& x: answer) {
cout << x << ' ';
}
cout << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 0;
cin >> t;
for(; t > 0; t--) {
solve();
}
return 0;
}