Last Updated: 29 Dec, 2020
Closest Number
Easy
Asked in companies
You are given two integers N and M. Can you find a number closest to N and divisible by M.
Here closest number to N means a number whose absolute difference is minimum with N. If there are two integers closest to N then the answer will be the one which is a smaller integer.
For Example:
Let N = 8 and M = 3
The numbers divisible by 3 are 3, 6, 9, …
From these numbers 9 is closest to 8. Thus, the answer is 9.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first and only line of each test case contains two integers N and M.
Output format :
For each test case, return an integer closest to N and divisible by M.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10^5
-10^9 <= N <= 10^9
1 <= M <= 10^9
Time limit: 1 sec
Approaches
The brute force approach is to loop over the number closest to N and find the one which is divisible by M.
- Run a loop from 0 to M-1:
- Check if N - i is divisible by M, if yes return N - i
- Check if N + i is divisible by M, if yes return N + i
The optimal approach is to find two closest numbers to N which are divisible by M and return the one which is closest to N.
We will find two number:
- Which is the largest number smaller than N and divisible by M.
- If N is negative, then num1 will be (N / M) * M - M
- Else, num1 will be (N / M) * M
- Which is the smallest number larger than N and divisible by M.
- If N is negative, then num2 will be (N / M)*M
- Else, num2 will be (N / M) * M + M
And return the one which is closest to N and if both are equally close to N then return num1 as it is smaller than num2.