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?
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;
while(temp<c)
{
twos = twos*2;
temp = twos - 1;
}
// cout<<temp<<"\n";
ll temp2 = temp - c;
if(temp2>0)
{
cout<<2<<"\n";
cout<<temp2<<" "<<temp<<"\n";
}
else
{
cout<<1<<"\n";
cout<<temp<<"\n";
}
}
return 0;
}
Consider the following input.
Input
1
5
Your Output
2
2 7
A_0 viz., 2 doesn’t satisfy the condition A_i = 2^x - 1.
Can someone help, I can’t figure out which case am I missing.
Solution: 52365564 | CodeChef
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]. LetX= 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;
}
1 Like
That’s really silly of me!
Thanks for pointing out
Thank you so much dear
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);
}
}
Are you trying to “Run” without Providing “Custom Input”?
Either way, there’s these errors:
[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
2 Likes