MassiveNumbers
SRM 236 · 2005-04-02 · by dimkadimon
Problem Statement
Massive numbers can be represented using the exponent notation. For example, 3^100 is 3 raised to the power of 100. 3 is the base and 100 is the exponent.
Suppose we want to compare two massive numbers. Instead of computing the exact value of each number we can rely on a useful mathematical trick. Suppose m = a^b and n = c^d are two massive numbers. Let R be a relationship operator: less, equal or greater. Then we have the following:
If b*Log(a) R d*Log(c) then it is also the case that m R n, where a, b, c, d, m and n are defined above.
So which is greater: 3^100 or 2^150? Let's do the math. 100*Log(3) = 47.7..., 150*Log(2) = 45.2.... Since 47.7 > 45.2, our rule tells us that 3^100 > 2^150.
Given two numbers numberA and numberB return the larger number formatted exactly the same as the input. numberA and numberB will be formatted as <base>^<exponent>. Constraints will ensure that numberA and numberB are not equal.
Notes
- In Java, the log of a number can be found with Math.log().
- In C++, the log of a number can be found with log().
- In C# and VB, the log of a number can be found with Math.Log().
Constraints
- numberA and numberB will contain between 3 and 9 characters inclusive.
- numberA and numberB will be formatted as
^ , where and are integers between 1 and 1000 inclusive. and cannot have leading zeroes. - The relative difference between b*Log(a) and d*Log(c) (where a, b, c and d are defined in the problem statement) will be at least 1e-6.
"3^100" "2^150" Returns: "3^100"
Above example.
"1^1000" "2^1" Returns: "2^1"
numberA is equal to 1, while numberB is equal to 2.
"893^605" "396^906" Returns: "396^906"
"999^1000" "1000^999" Returns: "999^1000"
"50^947" "236^230" Returns: "50^947"
Submissions are judged against all 30 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MassiveNumbers with a public method string getLargest(string numberA, string numberB) · 30 test cases · 2 s / 256 MB per case