Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

XOR-Based Number swap

EASYProblemSolveExternal Links

Description

Given two integers a and b, swap their values so that a holds the original value of b and b holds the original value of a.

The twist: you must accomplish this without using any temporary (extra) variable.

This classic problem tests your understanding of arithmetic properties and bitwise operations, and frequently appears in interviews at companies like Samsung.

Examples

Example 1

Input: a = 13, b = 9

Output: a = 9, b = 13

Explanation: After the swap, the variable a now holds 9 (the original value of b) and b now holds 13 (the original value of a). Both values have been exchanged successfully without using any additional storage.

Example 2

Input: a = 15, b = 8

Output: a = 8, b = 15

Explanation: The values are swapped: a becomes 8 and b becomes 15. The swap is performed in-place without any temporary variable.

Example 3

Input: a = 5, b = 5

Output: a = 5, b = 5

Explanation: When both values are identical, a swap produces the same result. This is an important edge case — the algorithm must handle equal values correctly without corrupting data.

Constraints

  • 1 ≤ a, b ≤ 10^6

Editorial

Brute Force

Intuition

The most natural way to swap two values is to use a helper container. Imagine you have two glasses — one filled with orange juice and the other with water. To swap their contents you would pour one glass into an empty third glass, then pour the second into the first, and finally pour from the third glass back into the second.

In programming, this "third glass" is a temporary variable. We store one value in it, overwrite that variable with the other, and then write the saved value into the second variable.

Although this approach uses an extra variable (which the problem prohibits), it is the starting point every beginner reaches, and it sets the stage for the cleverer techniques that follow.

Step-by-Step Explanation

Let's trace through with a = 13, b = 9:

Step 1: Create a temporary variable and store the value of a in it.

  • temp = a = 13
  • State: a = 13, b = 9, temp = 13

Step 2: Assign the value of b to a.

  • a = b = 9
  • State: a = 9, b = 9, temp = 13

Step 3: Assign the saved value (temp) to b.

  • b = temp = 13
  • State: a = 9, b = 13, temp = 13

Result: a = 9, b = 13 — values are swapped.

Swap Using Temporary Variable — Watch how a third variable (temp) acts as a holding area to safely exchange the values of a and b without losing either value.

Algorithm

  1. Create a temporary variable temp and store a in it: temp = a
  2. Copy b into a: a = b
  3. Copy the saved value into b: b = temp

Code

class Solution {
public:
    void swapNumbers(int &a, int &b) {
        int temp = a;
        a = b;
        b = temp;
    }
};
class Solution:
    def swapNumbers(self, a: int, b: int) -> tuple:
        temp = a
        a = b
        b = temp
        return a, b
class Solution {
    public int[] swapNumbers(int a, int b) {
        int temp = a;
        a = b;
        b = temp;
        return new int[]{a, b};
    }
}

Complexity Analysis

Time Complexity: O(1)

We perform exactly 3 assignment operations, each taking constant time. The number of operations does not depend on the input size.

Space Complexity: O(1)

We use one extra variable (temp). However, the problem explicitly requires swapping without a temporary variable, so while the space is technically O(1), this approach violates the problem constraint.

Why This Approach Is Not Efficient

The temporary-variable approach works correctly and is perfectly fine in general programming. However, the problem explicitly forbids the use of any extra variable.

The constraint "swap without a temporary variable" is the core challenge. We need a mathematical or bitwise trick that encodes both original values into the existing two variables themselves, eliminating the need for additional storage.

Key insight: certain mathematical operations are reversible. If we combine a and b using an operation that we can later undo, we can extract the original values back out. Addition/subtraction and XOR are two such reversible operations.

Better Approach - Arithmetic (Addition and Subtraction)

Intuition

Here is a clever trick using arithmetic: we temporarily encode the sum of both values into one of the variables.

Think of it this way: if you know the total weight of two packages and the weight of one package, you can deduce the other's weight by subtraction.

  1. First, store the sum of a and b into a. Now a holds both values encoded as their sum.
  2. Subtract the new a by b to get the original a — store this in b. Since a = (original_a + original_b), then a - b = original_a.
  3. Subtract the new a by the new b (which is original_a) to get original_b — store this in a. Since a still holds the sum, a - new_b = (original_a + original_b) - original_a = original_b.

The sum acts as a temporary encoding of both values inside a single variable, and subtraction peels them apart.

Step-by-Step Explanation

Let's trace through with a = 13, b = 9:

Step 1: Store the sum in a.

  • a = a + b = 13 + 9 = 22
  • State: a = 22, b = 9

Step 2: Extract original a into b by subtracting b from the sum.

  • b = a - b = 22 - 9 = 13
  • State: a = 22, b = 13

Step 3: Extract original b into a by subtracting the new b from the sum.

  • a = a - b = 22 - 13 = 9
  • State: a = 9, b = 13

Result: a = 9, b = 13 — values swapped without any temporary variable!

Arithmetic Swap Using Addition and Subtraction — Watch how the sum of both values is temporarily stored in variable a, then subtraction is used twice to extract the original values into their swapped positions.

Algorithm

  1. Store the sum of both values in a: a = a + b
  2. Extract the original a into b: b = a - b
  3. Extract the original b into a: a = a - b

Code

class Solution {
public:
    void swapNumbers(int &a, int &b) {
        a = a + b;
        b = a - b;
        a = a - b;
    }
};
class Solution:
    def swapNumbers(self, a: int, b: int) -> tuple:
        a = a + b
        b = a - b
        a = a - b
        return a, b
class Solution {
    public int[] swapNumbers(int a, int b) {
        a = a + b;
        b = a - b;
        a = a - b;
        return new int[]{a, b};
    }
}

Complexity Analysis

Time Complexity: O(1)

We perform exactly 3 arithmetic operations (one addition and two subtractions), each taking constant time.

Space Complexity: O(1)

No extra variables are used. The swap is performed entirely in-place using only the two given variables.

Why This Approach Is Not Efficient

While the arithmetic approach elegantly avoids a temporary variable, it has a critical flaw: integer overflow.

When we compute a + b, the result might exceed the maximum value that an integer can hold. In languages like C++ and Java, a 32-bit signed integer can store values up to 2,147,483,647. If a = 1,500,000,000 and b = 1,500,000,000, then a + b = 3,000,000,000, which overflows a 32-bit integer and produces a garbage value.

With this problem's constraints (a, b ≤ 10^6), the sum can be at most 2 × 10^6 = 2,000,000 — well within integer limits. But in general-purpose programming, where a and b could be much larger, the arithmetic approach is unsafe.

Key insight: we need an operation that is reversible like addition but cannot overflow. The XOR bitwise operation has this property — XOR operates on individual bits independently, so the result is always within the same bit range as the inputs.

Optimal Approach - XOR Bitwise Swap

Intuition

XOR (exclusive or) is a bitwise operation with a magical property: it is its own inverse. Applying XOR twice with the same value cancels out and returns the original.

Mathematically: if X = A ⊕ B, then X ⊕ B = A and X ⊕ A = B.

Think of XOR like a secret cipher where the key and the decryption method are the same operation. If you XOR a message with a key to encrypt it, you XOR the encrypted result with the same key to decrypt it.

Using this property for swapping:

  1. Encode both values into a by XOR-ing: a = a ⊕ b. Now a contains the combined "difference" of the two values at the bit level.
  2. Extract original a into b: b = a ⊕ b = (a ⊕ b) ⊕ b = a (since b ⊕ b cancels out).
  3. Extract original b into a: a = a ⊕ b = (a ⊕ b) ⊕ a = b (since a ⊕ a cancels out, remembering that b now holds original a).

No addition, no overflow risk — just pure bit manipulation.

Step-by-Step Explanation

Let's trace through with a = 13, b = 9.

First, let's see their binary representations:

  • 13 in binary = 1101
  • 9 in binary = 1001

Step 1: Compute a = a ⊕ b.

  • a = 13 ⊕ 9 = 1101 ⊕ 1001 = 0100 = 4
  • Bit-by-bit: (1⊕1=0), (1⊕0=1), (0⊕0=0), (1⊕1=0)
  • State: a = 4, b = 9

Step 2: Compute b = a ⊕ b.

  • b = 4 ⊕ 9 = 0100 ⊕ 1001 = 1101 = 13
  • Bit-by-bit: (0⊕1=1), (1⊕0=1), (0⊕0=0), (0⊕1=1)
  • State: a = 4, b = 13
  • Notice: b now holds the original value of a!

Step 3: Compute a = a ⊕ b.

  • a = 4 ⊕ 13 = 0100 ⊕ 1101 = 1001 = 9
  • Bit-by-bit: (0⊕1=1), (1⊕1=0), (0⊕0=0), (0⊕1=1)
  • State: a = 9, b = 13
  • Notice: a now holds the original value of b!

Result: a = 9, b = 13 — values swapped using only XOR, no overflow, no extra variable.

XOR Bitwise Swap — Step by Step — Watch how three XOR operations swap two values. The secondary row shows binary representations so you can see the bit-level operations.

Algorithm

  1. XOR both values and store in a: a = a ⊕ b
  2. XOR the new a with b to extract original a into b: b = a ⊕ b
  3. XOR the new a with new b to extract original b into a: a = a ⊕ b

Code

class Solution {
public:
    void swapNumbers(int &a, int &b) {
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
    }
};
class Solution:
    def swapNumbers(self, a: int, b: int) -> tuple:
        a = a ^ b
        b = a ^ b
        a = a ^ b
        return a, b
class Solution {
    public int[] swapNumbers(int a, int b) {
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
        return new int[]{a, b};
    }
}

Complexity Analysis

Time Complexity: O(1)

We perform exactly 3 XOR operations. Each XOR operates on fixed-width integers (32 or 64 bits) and takes constant time regardless of the values of a and b.

Space Complexity: O(1)

No extra variables or data structures are used. The swap is performed entirely in-place using only the two given variables. Unlike the arithmetic approach, XOR operates bit-by-bit and cannot overflow, making it safe for any integer values within the data type's range.