Lately, there has been a lot of video solutions coming out. I thought of writing a solution in the old format. There is already a video solution for this. You may check that out too.
PROBLEM LINK:
Setter - Farhan Hasin
DIFFICULTY:
Easy
PROBLEM:
Given two numbers A and B, maximize their sum. We are allowed to swap a digit in A with a digit in B at most once.
EXPLANATION:
Here, both A and B are in the range [1, 99]. So, they are either single or double digit.
The solution to the problem involves finding whether we want to do the swap. If yes, what is the correct swap so that it maximizes the sum.
In order to find the correct swap let’s first see -
- what an effective swap is; and
- what is the effect of the swap on the Sum = A + B.
Lets represent A and B in their decimal representation.
A = a_{1}a_{2}
B = b_{1}b_{2}
Here, if either A or B < 10 then, a_{1} or b_{1} = 0 respectively.
A swap is considered effective only if it is between digits of different decimal places i.e., if we swap a_{1} with b_{2} or a_{2} with b_{1} otherwise, the effect is 0.
For example, say we swap a_{2} and b_{2} or a_{1} and b_{1} then, the change in Sum is 0.
So, the swap will be between a ones-digit and a tens-digit of the two numbers.
Now that we know, what an effective swap is. Let’s see what is the effect of the swap on the sum.
Let Sum_{original} = A + B
Say we swap a_{2} and b_{1}. Then,
Sum_{new} = A + B + 10*(a_{2} - b_{1}) + (b_{1} - a_{2}) = A + B + 9*(a_{2} - b_{1})
Which can be generalized to,
Sum_{new} = A + B + 9*(d_{1s} - d_{10s}) where,
d_{1s} = ones-digit of one number and
d_{10s} = tens-digit of the other number.
Inorder to maximize the Sum we need to maximise diff = d_{1s} - d_{10s}.
Lets find all the pairs (d_{1s}, d_{10s}) for A and B. As mentioned before since A, B \in [1, 99]. There can be 0 to 2 valid pairs.
0 when both A, B < 10 and
2 when both A, B \geq 10.
So, the pairs are (b_{2}, a_{1}) and (a_{2}, b_{1}).
A pair is considered invalid if d_{10s} == 0 (i.e the relevent number is < 10) then its corresponding diff is 0 because the swap itself is invalid.
diff_{1} = b_{2} - a_{1} or 0 if a_{1} = 0 \Rightarrow A < 10
diff_{2} = a_{2} - b_{1} or 0 if b_{1} = 0 \Rightarrow B < 10
So, Sum_{max} = A + B + 9*max(0, diff_{1}, diff_{2}). Here, 0 represents no-swap scenario.
SOLUTION
Code (Python)
for t in range(int(input().strip())):
a, b = tuple(map(int, input().strip().split()))
diff1 = 0 if b < 10 else (a % 10 - b // 10)
diff2 = 0 if a < 10 else (b % 10 - a // 10)
res = a + b + 9 * max(0, diff1, diff2)
print(res)
Time Complexity = O(1)
Space Complexity = O(1)