Given two positive integers M and N, the task is to calculate the smallest number that needs to be added to M, to make it divisible by N.
Examples:
Input: M = 6, N = 7
Output: 1
Explanation: 1 is the smallest number that can be added to 6 to make it divisible by 7.Input: M = 100, N = 28
Output: 12
Approach: The idea is to find the smallest number greater than or equal to M, that is divisible by N, and then subtract M from it. To get the smallest multiple of N ? M, divide M + N by N. If the remainder is 0, then the value is M. Otherwise, the value is M + N – remainder.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the smallest// number greater than or equal// to N, that is divisible by kint findNum(int N, int K){ int rem = (N + K) % K; if (rem == 0) return N; else return N + K - rem;}// Function to find the smallest// number required to be added to// to M to make it divisible by Nint findSmallest(int M, int N){ // Stores the smallest multiple // of N, greater than or equal to M int x = findNum(M, N); // Return the result return x - M;}// Driver Codeint main(){ // Given Input int M = 100, N = 28; // Function Call cout << findSmallest(M, N); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to find the smallest// number greater than or equal// to N, that is divisible by kpublic static int findNum(int N, int K){ int rem = (N + K) % K; if (rem == 0) return N; else return N + K - rem;}// Function to find the smallest// number required to be added to// to M to make it divisible by Npublic static int findSmallest(int M, int N){ // Stores the smallest multiple // of N, greater than or equal to M int x = findNum(M, N); // Return the result return x - M;}// Driver Codepublic static void main(String args[]){ // Given Input int M = 100, N = 28; // Function Call System.out.println(findSmallest(M, N));}}// This code is contributed by SoumikMondal |
Python3
# Python3 program for the above approach# Function to find the smallest# number greater than or equal# to N, that is divisible by kdef findNum(N, K): rem = (N + K) % K if (rem == 0): return N else: return N + K - rem# Function to find the smallest# number required to be added to# to M to make it divisible by Ndef findSmallest(M, N): # Stores the smallest multiple # of N, greater than or equal to M x = findNum(M, N) # Return the result return x - M# Driver Codeif __name__ == '__main__': # Given Input M = 100 N = 28 # Function Call print(findSmallest(M, N)) # This code is contributed by ipg2016107 |
C#
// C# program for the above approachusing System; class GFG{ // Function to find the smallest// number greater than or equal// to N, that is divisible by kpublic static int findNum(int N, int K){ int rem = (N + K) % K; if (rem == 0) return N; else return N + K - rem;} // Function to find the smallest// number required to be added to// to M to make it divisible by Npublic static int findSmallest(int M, int N){ // Stores the smallest multiple // of N, greater than or equal to M int x = findNum(M, N); // Return the result return x - M;} // Driver Codepublic static void Main(){ // Given Input int M = 100, N = 28; // Function Call Console.WriteLine(findSmallest(M, N));}}// This code is contributed by susmitakundugoaldanga |
Javascript
<script>// Javascript program for the above approach// Function to find the smallest// number greater than or equal// to N, that is divisible by kfunction findNum(N, K){ var rem = (N + K) % K; if (rem == 0) return N; else return N + K - rem;}// Function to find the smallest// number required to be added to// to M to make it divisible by Nfunction findSmallest(M, N){ // Stores the smallest multiple // of N, greater than or equal to M var x = findNum(M, N); // Return the result return x - M;}// Driver Code// Given Inputvar M = 100, N = 28;// Function Calldocument.write(findSmallest(M, N));// This code is contributed by itsok</script> |
Output:
12
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
