We are missing some condition for n>2, can someone help to find special cases which our code is missing?

Question

Problem Statement:

You are given a sequence A1, A2,…, AN and you have to perform the following operation exactly X times:

• Choose two integers i and j such that 1≤i<j≤N.
• Choose a non-negative integer p.
• Change Ai to Ai⊕2p, and change Aj to Aj⊕2p, where ⊕ denotes bitwise XOR.

Find the lexicographically smallest sequence which can be obtained by performing this operation exactly X times.

A copy of the question can be https://www.codechef.com/DEC20B/problems/HXOR

Approach:

Here, we are dealing with N integers for X times operations, we are performing the xor function for all integers in an array with the power of 2 elements (2^p), p represents the non -ve integer.

For finding lexicographically smallest sequence, we are doing xor of each element until it becomes smallest and then we shift to the next element. Meanwhile, we also store the elements used in the previous steps to make pairs.

Test Case:

Input:

4 3

2 2 3 3

Output:

0 0 0 0

#include <bits/stdc++.h>

using namespace std;

#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define ll long long

#define pb push_back


ll bs(vector<ll> check, ll key){
    ll n = check.size();
    for(ll i=0; i<n; i++)
    {
        if(check[i]==key)
        {
            return i;
        }
    }

    return -1;
}

ll highestPowerof2(ll n)
{
   ll p = (ll)log2(n);
   return (ll)pow(2, p);
}

void smallestSequence()
{
    ll t;
    cin >> t;
    while(t--)
    {
        ll n,x;
        cin >> n >> x;
        ll a[n];
        for(ll i=0;i<n;i++)
        {
            cin >> a[i];
        }

        if(n==2)
        {
            for(int i=1; i<n; i++)
            {
                a[i]^=a[0];
            }
            a[0]=0;

            if(x%2==0)
            {
                a[0]^=1;
                for(int i=1; i<n; i++)
                {
                    a[i]^=1;
                }   
            }
            
            for(ll i=0;i<n;i++)
            {
                cout << a[i] <<" ";
            }
            cout << endl;
            continue;
        }
        ll temp = x;
        x = 2*x;

        vector <ll> check;
        ll i;
        ll flag=0;
        for(i=0;i<n;i++)
        {
            ll p=1;
            while(a[i]!=0 && x>0)
            {
                if(bs(check, highestPowerof2(a[i]))>=0)
                {
                    check.erase(check.begin()+ bs(check, highestPowerof2(a[i])));
                }
                else{
                    if(temp>0)
                    {
                        check.pb(highestPowerof2(a[i]));
                        temp--;
                    }else {
                        ll j = 0;
                        ll si = check.size();
                        for(j=0; j<si; j++)
                        {
                            ll res = check[j]^a[i];
                            if(res<=a[i])
                            {
                                a[i]^=check[j];
                                x--;
                                check.erase(check.begin()+j);
                                j--;
                                si--;
                            }
                        }
                        break;
                    }
                }
                a[i]^=highestPowerof2(a[i]);
                x--;
            }

            if(a[i]!=0)
            {
                flag=1;
            }
        }
        
        // if(flag==0 && temp>0 && (temp*2)==x)
        // {
        //  if(temp%2==1)
        //  {
        //      a[n-1]=a[n-2]=1;
        //  }
        // }

        while(x>=0 && !check.empty())
        {
            a[i-1]^=check[0];
            check.erase(check.begin());
        }

        for(ll i=0;i<n;i++)
        {
            cout << a[i] <<" ";
        }
        cout << endl;
    }
}


int main()
{
    fast;

    smallestSequence();

    return 0;
} 

Suggestions will be appreciated! I had been trying for this problem for almost 5 days now, I don't want a solution, I just want to know some special TCs where my code is giving WAs.

Answer 1

This is a on going contest. So this is the best i could help you.

Input:

1
4 4
1 2 3 4

Your output:

0 0 0 4

Right output:

0 0 1 5