Find the number closest to n and divisible by m
Given two integers n and m. The problem is to find the number closest to n and divisible by m. If there are more than one such number, then output the one having maximum absolute value. If n is completely divisible by m, then output n only.
Constraints: m != 0
Examples:
Input : n = 13, m = 4 Output : 12 Input : n = -15, m = 6 Output : -18 Both -12 and -18 are closest to -15, but -18 has the maximum absolute value.
We find value of n/m. Let this value be q. Then we find closest of two possibilities. One is q * m other is (m * (q + 1)) or (m * (q – 1)) depending on whether one of the given two numbers is negative or not.
Algorithm:
closestNumber(n, m) Declare q, n1, n2 q = n / m n1 = m * q if (n * m) > 0 n2 = m * (q + 1) else n2 = m * (q - 1) if abs(n-n1) < abs(n-n2) return n1 return n2
C++
// C++ implementation to find the number closest to n // and divisible by m #include <bits/stdc++.h> using namespace std; // function to find the number closest to n // and divisible by m int closestNumber( int n, int m) { // find the quotient int q = n / m; // 1st possible closest number int n1 = m * q; // 2nd possible closest number int n2 = (n * m) > 0 ? (m * (q + 1)) : (m * (q - 1)); // if true, then n1 is the required closest number if ( abs (n - n1) < abs (n - n2)) return n1; // else n2 is the required closest number return n2; } // Driver program to test above int main() { int n = 13, m = 4; cout << closestNumber(n, m) << endl; n = -15; m = 6; cout << closestNumber(n, m) << endl; n = 0; m = 8; cout << closestNumber(n, m) << endl; n = 18; m = -7; cout << closestNumber(n, m) << endl; return 0; } |
Java
// Java implementation to find the number closest to n // and divisible by m public class close_to_n_divisible_m { // function to find the number closest to n // and divisible by m static int closestNumber( int n, int m) { // find the quotient int q = n / m; // 1st possible closest number int n1 = m * q; // 2nd possible closest number int n2 = (n * m) > 0 ? (m * (q + 1 )) : (m * (q - 1 )); // if true, then n1 is the required closest number if (Math.abs(n - n1) < Math.abs(n - n2)) return n1; // else n2 is the required closest number return n2; } // Driver program to test above public static void main(String args[]) { int n = 13 , m = 4 ; System.out.println(closestNumber(n, m)); n = - 15 ; m = 6 ; System.out.println(closestNumber(n, m)); n = 0 ; m = 8 ; System.out.println(closestNumber(n, m)); n = 18 ; m = - 7 ; System.out.println(closestNumber(n, m)); } } // This code is contributed by Sumit Ghosh |
Python3
# Python 3 implementation to find # the number closest to n # Function to find the number closest # to n and divisible by m def closestNumber(n, m) : # Find the quotient q = int (n / m) # 1st possible closest number n1 = m * q # 2nd possible closest number if ((n * m) > 0 ) : n2 = (m * (q + 1 )) else : n2 = (m * (q - 1 )) # if true, then n1 is the required closest number if ( abs (n - n1) < abs (n - n2)) : return n1 # else n2 is the required closest number return n2 # Driver program to test above n = 13 ; m = 4 print (closestNumber(n, m)) n = - 15 ; m = 6 print (closestNumber(n, m)) n = 0 ; m = 8 print (closestNumber(n, m)) n = 18 ; m = - 7 print (closestNumber(n, m)) # This code is contributed by Nikita tiwari. |
C#
// C# implementation to find the // number closest to n and divisible by m using System; class GFG { // function to find the number closest to n // and divisible by m static int closestNumber( int n, int m) { // find the quotient int q = n / m; // 1st possible closest number int n1 = m * q; // 2nd possible closest number int n2 = (n * m) > 0 ? (m * (q + 1)) : (m * (q - 1)); // if true, then n1 is the required closest number if (Math.Abs(n - n1) < Math.Abs(n - n2)) return n1; // else n2 is the required closest number return n2; } // Driver program to test above public static void Main() { int n = 13, m = 4; Console.WriteLine(closestNumber(n, m)); n = -15; m = 6; Console.WriteLine(closestNumber(n, m)); n = 0; m = 8; Console.WriteLine(closestNumber(n, m)); n = 18; m = -7; Console.WriteLine(closestNumber(n, m)); } } // This code is contributed by Sam007 |
PHP
<?php // PHP implementation to find // the number closest to n and // divisible by m // function to find the number // closest to n and divisible by m function closestNumber( $n , $m ) { // find the quotient $q = (int) ( $n / $m ); // 1st possible closest number $n1 = $m * $q ; // 2nd possible closest number $n2 = ( $n * $m ) > 0 ? ( $m * ( $q + 1)) : ( $m * ( $q - 1)); // if true, then n1 is the // required closest number if ( abs ( $n - $n1 ) < abs ( $n - $n2 )) return $n1 ; // else n2 is the required // closest number return $n2 ; } // Driver Code $n = 13; $m = 4; echo closestNumber( $n , $m ), "\n" ; $n = -15; $m = 6; echo closestNumber( $n , $m ), "\n" ; $n = 0; $m = 8; echo closestNumber( $n , $m ), "\n" ; $n = 18; $m = -7; echo closestNumber( $n , $m ), "\n" ; // This code is contributed by jit_t ?> |
Javascript
<script> // Javascript implementation to find // the number closest to n and // divisible by m // function to find the number // closest to n and divisible by m function closestNumber(n, m) { // find the quotient let q = parseInt(n / m); // 1st possible closest number let n1 = m * q; // 2nd possible closest number let n2 = (n * m) > 0 ? (m * (q + 1)) : (m * (q - 1)); // if true, then n1 is the // required closest number if (Math.abs(n - n1) < Math.abs(n - n2)) return n1; // else n2 is the required // closest number return n2; } // Driver Code let n = 13; let m = 4; document.write(closestNumber(n, m) + "<br>" ); n = -15; m = 6; document.write(closestNumber(n, m) + "<br>" ); n = 0; m = 8; document.write(closestNumber(n, m) + "<br>" ); n = 18; m = -7; document.write(closestNumber(n, m) + "<br>" ); // This code is contributed by gfgking </script> |
Output:
12 -18 0 21
Time Complexity: O(1)
Auxiliary Space: O(1)