Apply Bitwise Operations to Make Strings Equal

Apply Bitwise Operations to Make Strings Equal - Problem

You are given two 0-indexed binary strings s and target of the same length n. You can do the following operation on s any number of times:

Choose two different indices i and j where 0 <= i, j < n.

Simultaneously replace s[i] with (s[i] OR s[j]) and s[j] with (s[i] XOR s[j]).

For example, if s = "0110", you can choose i = 0 and j = 2, then simultaneously replace s[0] with (s[0] OR s[2] = 0 OR 1 = 1), and s[2] with (s[0] XOR s[2] = 0 XOR 1 = 1), so we will have s = "1110".

Return true if you can make the string s equal to target, or false otherwise.

Input & Output

Example 1 — Basic Transformation

$ Input: s = "1010", target = "1100"

› Output: true

💡 Note: Choose i=1, j=2: s[1] OR s[2] = 1|1 = 1, s[1] XOR s[2] = 1^1 = 0. Result: "1100"

Example 2 — Impossible Case

$ Input: s = "0000", target = "1100"

› Output: false

💡 Note: Since s has no 1s, we cannot create any 1s using OR/XOR operations

Example 3 — Already Equal

$ Input: s = "1111", target = "1111"

› Output: true

💡 Note: s already equals target, no operations needed

Constraints

1 ≤ s.length ≤ 10⁵
s.length == target.length
s and target consist of only '0' and '1'

Visualization

Tap to expand

Understanding the Visualization

Input

Two binary strings s and target of same length

Operations

Apply OR and XOR operations on different indices

Goal

Check if s can be transformed into target

Key Takeaway

🎯 Key Insight: OR operations can only increase 1s, so strings with no 1s cannot reach targets with 1s

Asked in

G Google 15 f Meta 12 M Microsoft 8

The key insight is that OR operations can only create or maintain 1s, never eliminate them. If the source string has no 1s, we can only reach targets with no 1s. If source has 1s, we can reach most targets except the special case of all-1s target from non-all-1s source. Best approach is Mathematical Analysis with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(2^n)	O(2^n)	Try all possible operation sequences to reach target
Mathematical Analysis	O(n)	O(1)	Analyze operation properties to determine reachability

Brute Force Simulation — Algorithm Steps

Try all possible (i,j) pairs
Apply OR/XOR operations
Check if result matches target
Use BFS to explore all reachable states

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Start with string s and explore all possible operations

Apply Operations

For each state, try all (i,j) pairs with OR/XOR operations

Check Target

Return true if target is reached, false if all states explored

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_STATES 10000

typedef struct {
    char state[101];
} State;

bool solution(char* s, char* target) {
    if (strcmp(s, target) == 0) return true;
    
    int n = strlen(s);
    State visited[MAX_STATES];
    State queue[MAX_STATES];
    int visitedCount = 0;
    int front = 0, rear = 0;
    
    strcpy(queue[rear].state, s);
    rear++;
    strcpy(visited[visitedCount].state, s);
    visitedCount++;
    
    while (front < rear && rear < MAX_STATES) {
        State current = queue[front++];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    char newState[101];
                    strcpy(newState, current.state);
                    
                    int oldI = newState[i] - '0';
                    int oldJ = newState[j] - '0';
                    
                    int newI = oldI | oldJ;
                    int newJ = oldI ^ oldJ;
                    
                    newState[i] = '0' + newI;
                    newState[j] = '0' + newJ;
                    
                    if (strcmp(newState, target) == 0) return true;
                    
                    bool found = false;
                    for (int k = 0; k < visitedCount; k++) {
                        if (strcmp(visited[k].state, newState) == 0) {
                            found = true;
                            break;
                        }
                    }
                    
                    if (!found && visitedCount < MAX_STATES && rear < MAX_STATES) {
                        strcpy(visited[visitedCount].state, newState);
                        visitedCount++;
                        strcpy(queue[rear].state, newState);
                        rear++;
                    }
                }
            }
        }
    }
    
    return false;
}

int main() {
    char s[101], target[101];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    fgets(target, sizeof(target), stdin);
    target[strcspn(target, "\n")] = 0;
    
    bool result = solution(s, target);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Each position can be 0 or 1, leading to exponential state space exploration

⚠ Quadratic Growth

Space Complexity

O(2^n)

Need to store all visited states in BFS queue

⚠ Quadratic Space

12.5K Views

Medium Frequency

~25 min Avg. Time

387 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler