Robert Eisele
Engineer, Systems Architect and DBA

# Hackerrank: 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\\\Rightarrow & 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;
}

Go to overview