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;
}
Can someone please check why the code gives SIGCONT error?
I just started out with CC, a small help would be greatly appreciated.
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
void print(vector<ll> v){
cout << v.size() << endl;
sort(v.begin(), v.end());
for(ll i = 0; i < v.size(); i++){
cout << v[i] << " ";
}
cout << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ll t;
cin >> t;
while(t--){
vector<ll> v;
ll c, res = 0;
cin >> c;
for(ll i = 60; i >= 0; i--){
//stores the difference between c and the current bit
ll num1 = (1 << i) & c;
//stores the difference between the current bit and result
ll num2 = (1 << i) & res;
if (num1 != num2){
v.push_back((1 << (i + 1)) - 1);
res ^= ((1 << (i + 1)) - 1);
}
}
if(v.size() == 0){
v.push_back(1);
v.push_back(1);
}
print(v);
}
}
[simon@simon-laptop][13:36:03]
[~/devel/hackerrank/otherpeoples]>./compile-latest-cpp.sh
Compiling adarsh500-MINSZ.cpp
Executing command:
g++ -std=c++17 adarsh500-MINSZ.cpp -O3 -g3 -Wall -Wextra -Wconversion -DONLINE_JUDGE -D_GLIBCXX_DEBUG -fsanitize=undefined -ftrapv
adarsh500-MINSZ.cpp: In function ‘void print(std::__debug::vector<long long int>)’:
adarsh500-MINSZ.cpp:8:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll i = 0; i < v.size(); i++){
~~^~~~~~~~~~
Successful
[simon@simon-laptop][13:36:10]
[~/devel/hackerrank/otherpeoples]>echo "3
1
2
3
" | ./a.out
adarsh500-MINSZ.cpp:27:26: runtime error: shift exponent 60 is too large for 32-bit type 'int'
adarsh500-MINSZ.cpp:30:26: runtime error: shift exponent 60 is too large for 32-bit type 'int'
adarsh500-MINSZ.cpp:33:32: runtime error: shift exponent 33 is too large for 32-bit type 'int'
adarsh500-MINSZ.cpp:34:28: runtime error: shift exponent 33 is too large for 32-bit type 'int'
1
1
2
1 3
1
3
First test case works fine but not after that please tell mistake
P.S: In my code p stands for System.out.print
and pln - System.out.println
TC - for test case number
TTC - tootal no of test cases
void solve(int TC, int TTC) throws Exception{
long c = nl();
long orig = c;
long xor = 0;
LinkedList<Long>ans = new LinkedList<>();
for(long i=60;i>=0;i--){
long n1 = (1<<i)&c;
long n2 = (1<<i)&xor;
if(n1!=n2){
long temp = ((1<<(i+1))-1);
ans.addFirst(temp);
xor^=temp;
}
}
if(ans.size()==0){
ans.addFirst((long)1);
ans.addFirst((long)1);
}
pn(ans.size());
for(long ele: ans){
p(ele+" ");
}
if(TC!=TTC)
pn("");
}
if someone can help what’s wrong with this approach?
`#include<bits/stdc++.h>
using namespace std;
#define MOD 1e9+7
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define long long long int
long power(int i, int p)
{
if (p == 0) return 1;
long ans = 1;
for (int i=1;i<=p;i++)
ans*=2;
return ans;
}
vector<long> solve(long c)
{
if (c == 0)
{
vector<long> ans = {1,1};
return ans;
}
vector<int> arr;
while (c)
{
arr.push_back(c&1);
c = c>>1;
}
int i = 0;
vector<long> ans;
while (i < arr.size())
{
int n = arr[i];
while (arr[i] == n)
i++;
ans.push_back(power(2,i) - 1);
}
return ans;
}
int main(void) {
// your code goes here
fastIO
int t;
cin>>t;
while (t--)
{
long c;
cin>>c;
vector<long> ans = solve(c);
cout<<(int)ans.size()<<endl;
// sort(ans.begin(), ans.end());
for (auto e:ans)
cout<<e<<" ";
cout<<'\n';
}
return 0;
}`
[simon@simon-laptop][17:46:38]
[~/devel/hackerrank/otherpeoples]>./compile-latest-cpp.sh
Compiling rkr_rohit-MINSZ.cpp
Executing command:
g++ -std=c++17 rkr_rohit-MINSZ.cpp -O3 -g3 -Wall -Wextra -Wconversion -DONLINE_JUDGE -D_GLIBCXX_DEBUG -fsanitize=undefined -ftrapv
rkr_rohit-MINSZ.cpp: In function ‘long long int power(int, int)’:
rkr_rohit-MINSZ.cpp:7:16: warning: unused parameter ‘i’ [-Wunused-parameter]
long power(int i, int p)
^
rkr_rohit-MINSZ.cpp: In function ‘std::__debug::vector<long long int> solve(long long int)’:
rkr_rohit-MINSZ.cpp:32:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (i < arr.size())
~~^~~~~~~~~~~~
Successful
[simon@simon-laptop][17:46:53]
[~/devel/hackerrank/otherpeoples]>echo "3
1
2
3
" | ./a.out
/usr/include/c++/7/debug/vector:417:
Error: attempt to subscript container with out-of-bounds index 1, but
container only holds 1 elements.
Objects involved in the operation:
sequence "this" @ 0x0x7ffc7a113fc0 {
type = std::__debug::vector<int, std::allocator<int> >;
}
Aborted (core dumped)
it’s running fine with the provided test cases. I think the nature of all the test cases will be the same for this problem.
can you please provide the test case for which it is going out of bounds?
I have removed all the warnings provided above still, it is giving the wrong answer.
#include<bits/stdc++.h>
using namespace std;
#define MOD 1e9+7
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define long long long int
long power(int n, int p)
{
if (p == 0) return 1;
long ans = 1;
for (int i=1;i<=p;i++)
ans*=n;
return ans;
}
vector<long> solve(long c)
{
if (c == 0)
{
vector<long> ans = {1,1};
return ans;
}
vector<int> arr;
while (c)
{
arr.push_back(c&1);
c = c>>1;
}
int i = 0;
vector<long> ans;
while (i < (int)arr.size())
{
int n = arr[i];
while (arr[i] == n)
i++;
ans.push_back(power(2,i) - 1);
}
return ans;
}
int main(void) {
// your code goes here
fastIO
int t;
cin>>t;
while (t--)
{
long c;
cin>>c;
vector<long> ans = solve(c);
cout<<(int)ans.size()<<endl;
// sort(ans.begin(), ans.end());
for (auto e:ans)
cout<<e<<" ";
cout<<'\n';
}
return 0;
}
