Loading...
Loading...
Loading...
Arjun is writing code for a tiny chip in a college robotics project. The chip has no divide or multiply instruction, so the code must not use /, * or %. Addition, subtraction, comparisons and bit shifts are allowed.
Given two integers a and b, print the quotient a ÷ b, rounded toward zero, the same way Java's int division does: 7 ÷ -3 gives -2 and -7 ÷ 2 gives -3.
There is one exception. If the true quotient is larger than 2147483647, print 2147483647. This happens only for -2147483648 ÷ -1.
/, * or % in your codeExample 1
Input
7 -3
Output
-2
7 ÷ -3 is -2.33..., and rounding toward zero gives -2.
Example 2
Input
-2147483648 -1
Output
2147483647
The true answer 2147483648 does not fit in an int, so print 2147483647.
Try the problem first. Open one hint at a time.
Division is repeated subtraction, but subtracting b one at a time can take 2 × 10^9 steps.
Work with the absolute values in long, so -2147483648 can be made positive. Fix the sign at the end.
Subtract big chunks first: b shifted left by s is b × 2^s. Try s from 31 down to 0.
Each time b × 2^s fits into what is left of a, subtract it and add 2^s to the quotient.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor