MINSZ - Editorial

@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:

My approach was a little different. I assume that size of the array can be at most 3.
When n is of the form pow(2, x) then, answer can be 2 and elements must be n-1 and ((2n)-1).
When n is of the form (pow(2, x)-1) then, we can simply print n as it is.
When n is neither of the above two forms the size of the array must be 3.
We’ll calculate the answer as follows:
long long y=log2(n);
long long x=1LL<<(y);
cout<<3<<"\n";
cout<<abs(n-x)<<" “<<x-1<<” "<<(2
x)-1<<"\n";

I also handled the case where c=0;
Please help me through this… My code is also passing the testcase which @adityamonu_17 gave i.e. 1
8796093022208
Please someone help me through this.