There are two wooden sticks of lengths A and B respectively. Each of them can be cut into shorter sticks of integer lengths. Our goal is to construct the largest possible square. In order to do this, we want to cut the sticks in such a way as to achieve four sticks of the same length (note that there can be some leftover pieces). What is the longest side of the square that we can achieve?
Write a function:
class Solution {public int solution(int A, int B); }that, given two integers A and B, returns the side length of the largest square that we can obtain. If it is not possible to create any square, the function should return 0.
Examples:
- Given A = 10, B = 21, the function should return 7. We can split the second stick into three sticks of length 7 and shorten the first stick by 3.
- Given A = 13, B = 11, the function should return 5. We can cut two sticks of length 5 from each of the given sticks.
- Given A = 2, B = 1, the function should return 0. It is not possible to make any square from the given sticks.
- Given A = 1, B = 8, the function should return 2. We can cut stick B into four parts.
Write an efficient algorithm for the following assumptions:
- A and B are integers within the range [1..1,000,000,000].
This problem asks for the maximum possible square side that can be formed by cutting two sticks into integer-length pieces. For a candidate side length x, the number of usable pieces is floor(A / x) + floor(B / x), and we need at least 4 pieces to build a square. Because this feasibility condition is monotonic, the optimal solution is found efficiently with binary search over the side length range. Use 64-bit arithmetic when evaluating the piece count to avoid overflow for large inputs, and return 0 when no positive side length works.
