MINSZ - Editorial

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;
}
1 Like

@viraj_008

This should have been

if n == 0:
    and += "2\n1 1\n"

instead.

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

That was really helpful. Thank you : ))

1 Like

here is my code, I couldn’t get what I’m doing wrong. link

Consider the test input:

1
1152921504606846975

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("");
            
        }

See the post directly above yours.

1 Like

use long long int
#define ll long long

1 Like

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;
}`

Index out-of-bounds with sample testcase:

[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;
}
1 Like

:face_with_raised_eyebrow:

All the information you need was provided in that post :slight_smile:

bro plz check my code I didn’t found where I got wrong…
(CodeChef: Practical coding for everyone)

please can anyone find what is the mistake in my code.

int main()
{ 
  ios_base::sync_with_stdio(false); cin.tie(NULL);
  ll tt;
  cin>>tt;

  while(tt--)
   {
      ll c; cin>>c;
      vector<unsigned long long int>v;
      int count=0;
      for(int i=0;i<=60;i++)
      {
          if(c&(1ull<<i)!=0)
          { 
            count++;
            v.push_back(1ull<<i);
          }
      }
      
      cout<<count<<endl;
      for(auto x:v)cout<<x<<" ";
        cout<<endl;

   }
   return 0;
}

Please post the rest of it :slight_smile: