XORRY2 - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: munch_01
Tester: raysh_07
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You’re given an integer X.
Find the number of pairs (A, B) such that:

  • 0 \leq A \leq B \leq X
  • A\oplus B = X
  • (B-A) is as small as possible across all pairs satisfying the first two conditions.

EXPLANATION:

It is recommended to read the editorial of XORRY1 first, since this will continue from there.

As before, let x_1 \lt x_2 \lt\ldots\lt x_k be the set bits in the binary representation of X.
We observed that:

  • One solution is obtained by setting B = 2^{x_k} and A = 2^{x_1} + 2^{x_2} + \ldots + 2^{x_{k-1}}.
  • Moving any of these x_i from A over to B will increase the difference, and so isn’t optimal.
  • For all bits that aren’t one of the x_i, they must be set in either both A and B, or they must not be.
    However, whether they are set or not doesn’t affect the difference (B-A) at all.

So, each bit other than the x_i has a choice: it can be either set or unset.
However, we need to ensure that A and B don’t exceed X while doing this.
To that end, observe that:

  • Setting any bit higher than x_k will cause both A and B to exceed X, so we can’t do this.
  • Setting any bit between x_{k-1} and x_k will cause B to exceed X so we can’t do this either.
  • Setting any bit lower than x_{k-1} won’t cause any issues, since even if all of them were set, B's value is bounded above by 2^{x_k} + 2^{x_{k-1}} which can’t exceed X.

This means, if there are m bits below x_{k-1} that are ‘free’, the answer is simply 2^m — for each of them, we can independently choose whether to set it or not.
Finding the number of such bits is easy in \mathcal{O}(\log X) since you can just iterate each bit to check.

TIME COMPLEXITY:

\mathcal{O}(\log X) per testcase.

CODE:

Tester's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

struct input_checker {
    string buffer;
    int pos;

    const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    const string number = "0123456789";
    const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    const string lower = "abcdefghijklmnopqrstuvwxyz";

    input_checker() {
        pos = 0;
        while (true) {
            int c = cin.get();
            if (c == -1) {
                break;
            }
            buffer.push_back((char) c);
        }
    }

    int nextDelimiter() {
        int now = pos;
        while (now < (int) buffer.size() && !isspace(buffer[now])) {
            now++;
        }
        return now;
    }

    string readOne() {
        assert(pos < (int) buffer.size());
        int nxt = nextDelimiter();
        string res;
        while (pos < nxt) {
            res += buffer[pos];
            pos++;
        }
        return res;
    }

    string readString(int minl, int maxl, const string &pattern = "") {
        assert(minl <= maxl);
        string res = readOne();
        assert(minl <= (int) res.size());
        assert((int) res.size() <= maxl);
        for (int i = 0; i < (int) res.size(); i++) {
            assert(pattern.empty() || pattern.find(res[i]) != string::npos);
        }
        return res;
    }

    int readInt(int minv, int maxv) {
        assert(minv <= maxv);
        int res = stoi(readOne());
        assert(minv <= res);
        assert(res <= maxv);
        return res;
    }

    long long readLong(long long minv, long long maxv) {
        assert(minv <= maxv);
        long long res = stoll(readOne());
        assert(minv <= res);
        assert(res <= maxv);
        return res;
    }

    auto readInts(int n, int minv, int maxv) {
        assert(n >= 0);
        vector<int> v(n);
        for (int i = 0; i < n; ++i) {
            v[i] = readInt(minv, maxv);
            if (i+1 < n) readSpace();
        }
        return v;
    }

    auto readLongs(int n, long long minv, long long maxv) {
        assert(n >= 0);
        vector<long long> v(n);
        for (int i = 0; i < n; ++i) {
            v[i] = readLong(minv, maxv);
            if (i+1 < n) readSpace();
        }
        return v;
    }

    void readSpace() {
        assert((int) buffer.size() > pos);
        assert(buffer[pos] == ' ');
        pos++;
    }

    void readEoln() {
        assert((int) buffer.size() > pos);
        assert(buffer[pos] == '\n');
        pos++;
    }

    void readEof() {
        assert((int) buffer.size() == pos);
    }
};

input_checker inp;

const int T = 1e5;
const int N = 1e9;

void Solve() 
{
    int n = inp.readInt(1, N);
    inp.readEoln();
    int ans = 1;
    int cnt = 0;
    for (int i = 31; i >= 0; i--){
        if (n >> i & 1){
            cnt++;
        } else {
            if (cnt >= 2) ans *= 2;
        }
    }

    cout << ans << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    t = inp.readInt(1, T);
    inp.readEoln();

    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }

    inp.readEof();

    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}
Editorialist's code (Python) 
for _ in range(int(input())):
    x = int(input())
    a, b = 0, 0
    for i in range(30):
        if x & 2**i:
            a += b
            b = 2**i
    ans = 1
    for i in range(30):
        if 2**i <= a and (x & 2**i == 0): ans *= 2
    print(ans)