LeetCode Problem 3783

Difficulty: 🟢 Easy
Topics: Math

Solution

LeetCode 3783 - Mirror Distance of an Integer

Problem Understanding

The problem gives us a positive integer n and asks us to compute its mirror distance.

The mirror distance is defined as:

$$|n - reverse(n)|$$

where reverse(n) is the integer obtained by reversing the decimal digits of n, and |x| denotes the absolute value.

For example, if n = 25, reversing its digits produces 52. The mirror distance is therefore:

$$|25 - 52| = 27$$

The input consists of a single integer n, and the output should be a single integer representing the absolute difference between n and its reversed form.

The constraint is:

• 1 <= n <= 10^9

This tells us that the number contains at most 10 decimal digits. Since the input size is extremely small, we do not need sophisticated algorithms. Even processing each digit individually is essentially constant time.

There are several edge cases worth noticing:

• Single digit numbers such as 7, whose reverse is identical to themselves.
• Numbers ending in zero, such as 10. Reversing 10 gives "01", which corresponds to integer 1.
• Palindromic numbers such as 121, where the reverse equals the original number.
• The maximum allowed value, 10^9, which reverses to 1.

The problem guarantees that n is always a positive integer, so we do not need to handle negative values.

Approaches

Brute Force Approach

A straightforward solution is to convert the number into a string, reverse the string, convert it back into an integer, and then compute the absolute difference.

For example:

• Convert 25 to "25"
• Reverse to "52"
• Convert back to integer 52
• Return abs(25 - 52)

This approach is simple and correct because string reversal directly produces the digit-reversed representation required by the problem.

Optimal Approach

We can also reverse the number mathematically without using strings.

The key observation is that reversing digits can be done by repeatedly extracting the last digit and appending it to a new number.

For example, for 1234:

• Take digit 4, reversed becomes 4
• Take digit 3, reversed becomes 43
• Take digit 2, reversed becomes 432
• Take digit 1, reversed becomes 4321

At the end, we compute the absolute difference between the original number and the reversed number.

Because the input contains at most 10 digits, this process is extremely efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(d)	O(d)	Reverse using string operations
Optimal	O(d)	O(1)	Reverse digits mathematically

Here, d is the number of digits in n.

Algorithm Walkthrough

Optimal Algorithm

1. Store the original value of n because we will modify a working copy while reversing its digits.
2. Initialize a variable reversed_num to 0. This variable will gradually build the reversed integer.
3. While the working copy of n is greater than zero, extract its last digit using n % 10.
4. Append the extracted digit to the end of reversed_num by computing:

reversed_num = reversed_num * 10 + digit

Multiplying by 10 shifts all existing digits one position to the left, creating space for the new digit. 5. Remove the last digit from n using integer division:

n //= 10

6. Continue until all digits have been processed.
7. Compute the absolute difference between the original number and reversed_num.
8. Return the result.

Why it works

At every iteration, the algorithm removes the rightmost digit from the original number and appends it to the right side of reversed_num. After all digits have been processed, the digits appear in exactly the opposite order, which is precisely the definition of the reversed integer. Since the final step computes abs(original - reversed_num), the returned value is exactly the mirror distance required by the problem.

Python Solution

class Solution:
    def mirrorDistance(self, n: int) -> int:
        original = n
        reversed_num = 0

        while n > 0:
            digit = n % 10
            reversed_num = reversed_num * 10 + digit
            n //= 10

        return abs(original - reversed_num)

The implementation begins by storing the original value in original, since the variable n will be consumed during digit extraction.

The variable reversed_num accumulates the reversed digits. Each iteration extracts the last digit using modulo arithmetic and appends it to the growing reversed number.

After processing all digits, the algorithm computes and returns the absolute difference between the original number and its reversed form.

This directly follows the mathematical digit-reversal procedure described in the algorithm walkthrough.

Go Solution

func mirrorDistance(n int) int {
	original := n
	reversedNum := 0

	for n > 0 {
		digit := n % 10
		reversedNum = reversedNum*10 + digit
		n /= 10
	}

	if original > reversedNum {
		return original - reversedNum
	}

	return reversedNum - original
}

The Go implementation mirrors the Python logic almost exactly.

One small difference is the computation of the absolute value. Go does not provide a built in integer abs function in the standard language syntax, so we compare the two values and return the positive difference manually.

The constraints ensure that all intermediate values easily fit within Go's integer range.

Worked Examples

Example 1

Input:

n = 25

Initial state:

Variable	Value
original	25
n	25
reversed_num	0

Iteration 1:

Operation	Result
digit = 25 % 10	5
reversed_num = 0 * 10 + 5	5
n = 25 // 10	2

Iteration 2:

Operation	Result
digit = 2 % 10	2
reversed_num = 5 * 10 + 2	52
n = 2 // 10	0

Final values:

Variable	Value
original	25
reversed_num	52

Answer:

abs(25 - 52) = 27

Output:

27

Example 2

Input:

n = 10

Initial state:

Variable	Value
original	10
n	10
reversed_num	0

Iteration 1:

Operation	Result
digit = 10 % 10	0
reversed_num = 0
n = 1

Iteration 2:

Operation	Result
digit = 1 % 10	1
reversed_num = 1
n = 0

Final values:

Variable	Value
original	10
reversed_num	1

Answer:

abs(10 - 1) = 9

Output:

9

Example 3

Input:

n = 7

Initial state:

Variable	Value
original	7
n	7
reversed_num	0

Iteration 1:

Operation	Result
digit = 7 % 10	7
reversed_num = 7
n = 0

Final values:

Variable	Value
original	7
reversed_num	7

Answer:

abs(7 - 7) = 0

Output:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(d)	Each digit is processed exactly once
Space	O(1)	Only a few integer variables are used

The algorithm performs one iteration per decimal digit of the input number. Since n ≤ 10^9, there are at most 10 digits, making the runtime effectively constant in practice. The memory usage remains constant because no auxiliary data structures are allocated.

Test Cases

sol = Solution()

assert sol.mirrorDistance(25) == 27      # Example 1
assert sol.mirrorDistance(10) == 9       # Example 2, trailing zero
assert sol.mirrorDistance(7) == 0        # Example 3, single digit

assert sol.mirrorDistance(1) == 0        # Minimum value
assert sol.mirrorDistance(11) == 0       # Two-digit palindrome
assert sol.mirrorDistance(121) == 0      # Multi-digit palindrome

assert sol.mirrorDistance(100) == 99     # Multiple trailing zeros
assert sol.mirrorDistance(1200) == 1179  # Reverse drops leading zeros

assert sol.mirrorDistance(123) == 198    # General case
assert sol.mirrorDistance(12345) == 41976  # Larger general case

assert sol.mirrorDistance(1000000000) == 999999999  # Maximum constraint

Test Summary

Test	Why
25	Basic example
10	Reverse contains leading zero
7	Single digit number
1	Minimum constraint
11	Two-digit palindrome
121	Multi-digit palindrome
100	Multiple trailing zeros
1200	Leading zeros disappear after reversal
123	Typical non-palindrome
12345	Larger general input
1000000000	Maximum allowed value

Edge Cases

Single-Digit Numbers

For any single-digit number, reversing the digits produces the same number. A careless implementation might overcomplicate this case, but the digit-reversal loop naturally handles it. After one iteration, the reversed value equals the original value, producing a mirror distance of zero.

Numbers Ending with Zero

Values such as 10, 100, and 1200 are important because reversing them creates leading zeros. For example, reversing 1200 conceptually gives "0021", which corresponds to integer 21. The mathematical reversal process automatically ignores leading zeros because integers do not store them, producing the correct result.

Palindromic Numbers

Numbers like 11, 121, and 12321 read the same forwards and backwards. Their reversed form is identical to the original value, so the mirror distance should be zero. Since the algorithm constructs the exact reverse, it correctly returns zero for all palindromic inputs.

Maximum Constraint Value

The largest input is 10^9. Reversing it produces 1, resulting in a large difference. The algorithm still works correctly because it only processes a small number of digits and all intermediate values remain within standard integer limits.