2153B Approach

2153B - Bitwise Reversion

Problem Understanding

Given three integers x, y, and z, we need to check if they satisfy a specific bitwise condition.

Approach

Key Insight

The solution converts all three numbers to their binary representations and pads them to the same length with leading zeros. Then it checks a bitwise constraint across all bit positions.

Algorithm Steps

Decimal to Binary Conversion
- Convert x, y, z to binary strings using bitwise operations
- Each number is converted by repeatedly checking the least significant bit (LSB) using n & 1
- Then right-shifting by 1 using n >>= 1
Padding Binary Strings
- Find the maximum length among the three binary representations
- Pad shorter strings with leading zeros to match this maximum length
- This ensures all three numbers have the same bit positions for comparison
Bitwise Validation
- For each bit position, check the following conditions:
  - If bit positions in x and y are both 1, then bit position in z must be 1
  - If bit positions in y and z are both 1, then bit position in x must be 1
  - If bit positions in x and z are both 1, then bit position in y must be 1
These conditions essentially check if whenever two of the three numbers have a ‘1’ bit at the same position, the third one must also have a ‘1’ bit at that position.
Output
- If all bit positions satisfy the constraints, output “YES”
- Otherwise, output “NO”

Complexity Analysis

Time Complexity: O(log max(x, y, z)) for binary conversion + O(log max(x, y, z)) for validation = O(log N) where N = max(x, y, z)
Space Complexity: O(log N) for storing binary strings

Example Logic

For x = 5 (101), y = 3 (011), z = 7 (111):

Padded: x = 101, y = 011, z = 111
Position 0: x[0]=1, y[0]=0, z[0]=1 → x and z are 1, so y must be 1 (but it’s 0) → Check fails? Actually we need to verify the exact constraint…
The algorithm checks if the constraint is satisfied or violated

Code Explanation

decimalToBinary(): Converts a number to binary string efficiently
solve(): Main logic that performs the validation
The triple loop checks all three pairs of conditions for each bit position

C++ Solution

#include <bits/stdc++.h>
using namespace std;

// --- Macros ---
#define ll long long

// --- Solution ---

// ==========================================
// 1. DECIMAL TO BINARY (Bitwise)
// Complexity: O(log N)
// ==========================================
string decimalToBinary(long long n) {
    if (n == 0) return "0";
   
    string binary = "";
    binary.reserve(64); 
    
    if (n > 0) {
        while (n > 0) {
            binary += (n & 1) + '0';
            n >>= 1;
        }
        reverse(binary.begin(), binary.end());
    } 
    return binary;
}


void solve() {
	ll x,y,z;
	cin >> x >> y >> z;

	string X = decimalToBinary(x);
	string Y = decimalToBinary(y);
	string Z = decimalToBinary(z);

	ll mx = max(X.size(),max(Y.size(),Z.size()));

	if(X.size() < mx){
		string t;
		for(int i=1;i<=(mx-X.size());i++){
			t.push_back('0');
		}
		for(auto c : X){
			t.push_back(c);
		}
		X = t;
	}

	if(Y.size() < mx){
		string t;
		for(int i=1;i<=(mx-Y.size());i++){
			t.push_back('0');
		}
		for(auto c : Y){
			t.push_back(c);
		}
		Y = t;
	}

	if(Z.size() < mx){
		string t;
		for(int i=1;i<=(mx-Z.size());i++){
			t.push_back('0');
    }
		for(auto c : Z){
			t.push_back(c);
		}
		Z = t;
	}
	bool flag = true;
	for(int i = 0; i < mx; i++){
		if(X[i] == Y[i] && X[i] == '1'){
			if(Z[i] != '1'){
				flag = false;
				break;
			}
		}
		if(Y[i] == Z[i] && Y[i] == '1'){
			if(X[i] != '1'){
				flag = false;
				break;
			}
		}
		if(X[i] == Z[i] && X[i] == '1'){
			if(Y[i] != '1'){
				flag = false;
				break;
			}
		}
	}

	cout<<((flag==true)?"YES\n":"NO\n");
    
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll T = 1;
    cin >> T;
    while(T--){
        solve();
        }
    return 0;
    }

Alternate C++ Solution (Concise Bitwise)

#include <bits/stdc++.h>
using namespace std;

// --- Solution ---

void solve() {
	ll x,y,z;
	cin >> x >> y >> z;

	ll X = x & y;
	ll Y = y & z;
	ll Z = x & z;

	cout<<((X==Y && Y==Z) ? "YES\n" : "NO\n");
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll T = 1;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

Approach for the Concise Bitwise Solution

This alternate solution leverages a key bitwise property:

For three integers x, y, z, compute the pairwise ANDs: (x & y), (y & z), and (x & z).
If all three results are equal, output “YES”; otherwise, output “NO”.

Why does this work?

The AND operation between two numbers results in a number where each bit is 1 only if both numbers have a 1 in that position.
If (x & y) == (y & z) == (x & z), it means that for every bit position, the set of 1s is consistent across all pairs.
This is a much more concise check for the same property as the longer solution: whenever two numbers have a 1 in a bit position, the third must also have a 1 there.

Steps:

Read x, y, z.
Compute X = x & y, Y = y & z, Z = x & z.
If X == Y == Z, print “YES”; else, print “NO”.

Complexity:

Time: O(1) (since bitwise AND is a single operation for fixed-width integers)
Space: O(1)

This approach is optimal and elegant for this specific bitwise property check.

🔒 Private Site