Hackerrank Solution: Closest Number

Original Problem

You are given 3 numbers \(a, b\) and \(x\). You need to output the multiple of \(x\) which is closest to \(a^b\). If more than one answer exists, display the smallest one.

Input Format

The first line contains \(T\), the number of testcases.
\(T\) lines follow, each line contains 3 space separated integers (\(a, b\) and \(x\) respectively)

Constraints

\(1\leq T\leq 10^5\)
\(1\leq x\leq 10^9\)
\(0<a^b\leq 10^9\)
\(1\leq a\leq 10^9\)
\(-10^9\leq b\leq 10^9\)

Output Format

For each test case, output the multiple of x which is closest to \(a^b\)

Sample Input

3
349 1 4
395 1 7
4 -2 2

Sample Output

348
392
0

Explanationy

The closest multiple of 4 to 349 is 348.
The closest multiple of 7 to 395 is 392.
The closest multiple of 2 to 1/16 is 0.

Solution

The numbers we get stay in the following relationship with eachother, using a multiplier \(m\in\mathbb{N}\):

\[\begin{array}{rrl} & mx&=a^b\\ \Leftrightarrow & m&=\frac{a^b}{x}\\ \Leftrightarrow & m&=\exp(b\log(a)-\log(x)) \end{array}\]

Knowing the multiplier almost solves the problem. We now need to round the result to find the closest integer as a valid multiple. This also solves the problem that the smaller one must be chosen, if multiple possible solutions are there:

\[m = \left[\exp(b\log(a)-\log(x))\right]\]

In order to find the final multiple, we need to multply the multiplier \(m\) with the base \(x\), which results in the following C++ code:

#include <iostream>
#include <cmath>

int main() {

    std::cout.precision( 10 );

    int T;
    std::cin >> T;
    for (int i = 0; i < T; i++) {
        double a, b, x;
        std::cin >> a >> b >> x;

        std::cout << round(exp(b * log(a) - log(x))) * x << std::endl;
    }
    return 0;
}