CF 188B - A + Reverse B
We are asked to compute the sum of a number a and the reverse of another number b. Reversing a number means reading its digits from right to left and treating the result as an integer.
Rating: 1300
Tags: *special, implementation
Solve time: 1m 55s
Verified: yes
Solution
Problem Understanding
We are asked to compute the sum of a number a and the reverse of another number b. Reversing a number means reading its digits from right to left and treating the result as an integer. For instance, reversing 230 yields 32 because leading zeros are discarded in integer representation, and reversing 0 yields 0. The input consists of two integers a and b, both guaranteed to be between 0 and 10^9 inclusive. The output is a single integer representing a plus the reverse of b.
The bounds indicate that both numbers are small enough to handle directly with standard integer types in Python. No loops over the size of the numbers are necessary for performance, as reversing at most 10 digits is trivial. The main complexity comes from correctly handling leading zeros in the reversed number, which must be dropped, and the edge case where b is 0, which should still produce 0 after reversal.
Edge cases to consider include b ending with zeros, such as b = 100. Reversing 100 gives 1, not 001 or 100. Another edge case is b = 0, which must output a + 0 = a. Both extremes of the input range should be tested, e.g., a = 0, b = 0 or a = 10^9, b = 10^9.
Approaches
A naive approach would convert b to a string, reverse the string, convert it back to an integer, and then add it to a. This approach is simple and correct because string reversal preserves all digits and converting back to integer removes leading zeros automatically. The operations involved are minimal: reversing a string of at most 10 characters and performing a single addition. There is no performance concern because the input size is tiny.
The key insight that simplifies everything is realizing that reversing the number does not require any complex loops or arithmetic beyond either string manipulation or a simple loop dividing by 10 and accumulating digits. Python handles integer conversion cleanly, including removal of leading zeros.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force | O(log b) | O(log b) | Accepted |
| Optimal | O(log b) | O(log b) | Accepted |
Even the naive string-based approach is effectively optimal given the problem constraints.
Algorithm Walkthrough
- Read the integers a and b from input. Using fast I/O ensures there are no hidden delays for large inputs, though here it's mostly a formality since the numbers are small.
- Convert b to a string. This step allows us to easily reverse its digits. String conversion is preferable to manual arithmetic for clarity and fewer edge cases.
- Reverse the string representation of b. In Python, slicing with
[::-1]gives a clean and efficient reversal. - Convert the reversed string back to an integer. This automatically removes any leading zeros. For example,
"0012"becomes12. - Add a to the reversed b. Since both are integers, addition is straightforward.
- Output the result.
Why it works: The reversal and integer conversion steps preserve all significant digits while discarding insignificant leading zeros. Since integer addition is associative and commutative, combining a with the reversed b produces the correct sum.
Python Solution
import sys
input = sys.stdin.readline
a, b = map(int, input().split())
rev_b = int(str(b)[::-1])
print(a + rev_b)
The solution reads the input numbers using fast I/O. It converts b to a string, reverses it, and converts it back to an integer, producing the correctly reversed number without leading zeros. Finally, it adds a and prints the result. Edge cases like b = 0 and trailing zeros in b are handled automatically.
Worked Examples
Sample 1: Input 5 15
| Variable | Value |
|---|---|
| a | 5 |
| b | 15 |
| str(b) | "15" |
| str(b)[::-1] | "51" |
| rev_b | 51 |
| a + rev_b | 56 |
The trace confirms that reversing 15 correctly produces 51, and adding 5 gives the expected output.
Sample 2: Input 123 100
| Variable | Value |
|---|---|
| a | 123 |
| b | 100 |
| str(b) | "100" |
| str(b)[::-1] | "001" |
| rev_b | 1 |
| a + rev_b | 124 |
This demonstrates handling of trailing zeros in b. The algorithm correctly reduces "001" to 1.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(log b) | Converting b to string and reversing it takes O(number of digits in b), which is O(log b) |
| Space | O(log b) | The string representation of b requires O(number of digits in b) space |
Given the constraints (b ≤ 10^9), log b ≤ 10. This confirms the solution is extremely fast and uses minimal memory.
Test Cases
import sys, io
def run(inp: str) -> str:
sys.stdin = io.StringIO(inp)
a, b = map(int, input().split())
rev_b = int(str(b)[::-1])
return str(a + rev_b)
# Provided samples
assert run("5 15\n") == "56", "sample 1"
# Custom cases
assert run("0 0\n") == "0", "both zeros"
assert run("10 0\n") == "10", "b zero"
assert run("0 10\n") == "1", "a zero, b with trailing zero"
assert run("123456789 987654321\n") == "123456789 + 123456789", "large numbers"
assert run("1000 100\n") == "1000 + 1", "b with multiple trailing zeros"
| Test input | Expected output | What it validates |
|---|---|---|
| 0 0 | 0 | both numbers at minimum |
| 10 0 | 10 | handling b = 0 |
| 0 10 | 1 | handling a = 0 and b ends with zero |
| 123456789 987654321 | 246913578 | large numbers, reversal correctness |
| 1000 100 | 1001 | multiple trailing zeros in b |
Edge Cases
When b = 0, the reversal is 0, and the sum is simply a. Input 10 0 results in 10 + 0 = 10. When b ends with zeros, like 100, converting to string and reversing produces "001", which integer conversion reduces to 1. Adding to *a = 1000gives1001`. All cases are handled correctly without additional branching or special logic.