Given a number N and a number K, the task is to find the smallest number greater than or equal to N which is divisible by K.
Examples:
Input: N = 45, K = 6 Output: 48 48 is the smallest number greater than or equal to 45 which is divisible by 6. Input: N = 11, K = 3 Output: 12
Approach:
Approach to solve this problem would be to start from N and check each number one by one until we find a number that is divisible by K. We can use a while loop to keep incrementing N until we find a number that is divisible by K.
Here are the steps of approach:
- We start with N and check each number one by one until we find a number that is divisible by K.
- We use a while loop to keep incrementing N until we find a number that is divisible by K.
- Once we find the smallest number greater than or equal to N that is divisible by K, we return it.
Below is the implementation of the above approach:
C++
// C++ implementation of 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){ while (N % K != 0) { N++; } return N;}// Driver codeint main(){ int N = 45, K = 6; cout << "Smallest number greater than or equal to " << N << "\nthat is divisible by " << K << " is " << findNum(N, K); return 0;} |
Output
Smallest number greater than or equal to 45 that is divisible by 6 is 48
Time Complexity: O(K), where K is the divisor. The while loop will run at most K times before finding a number that is divisible by K.
Space Complexity: O(1), because we are only using a constant amount of extra space to store the input variables
Approach: The idea is to divide the N+K by K. If the remainder is 0 then print N else print N + K – remainder.
Below is the implementation of the above approach :
C++
// C++ implementation of 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;}// Driver codeint main(){ int N = 45, K = 6; cout << "Smallest number greater than or equal to " << N << "\nthat is divisible by " << K << " is " << findNum(N, K); return 0;} |
Java
// Java implementation of the above approachpublic class GFG{ // Function to find the smallest number // greater than or equal to N // that is divisible by k static int findNum(int N, int K) { int rem = (N + K) % K; if (rem == 0) return N; else return N + K - rem; } // Driver Code public static void main(String []args){ int N = 45, K = 6; System.out.println("Smallest number greater than or equal to " + N +"\nthat is divisible by " + K + " is " + findNum(N, K)); } // This code is contributed by ANKITRAI1} |
Python
# Python 3 implementation of the # above approach # Function to find the smallest number # greater than or equal to N # that is divisible by k def findNum(N, K): rem = (N + K) % K; if (rem == 0): return N else: return (N + K - rem) # Driver CodeN = 45K = 6print('Smallest number greater than', 'or equal to' , N, 'that is divisible by', K, 'is' , findNum(45, 6))# This code is contributed by Arnab Kundu |
C#
// C# implementation of the above approachpublic class GFG{ // Function to find the smallest number // greater than or equal to N // that is divisible by k static int findNum(int N, int K) { int rem = (N + K) % K; if (rem == 0) return N; else return N + K - rem; } // Driver Code static void Main(){ int N = 45, K = 6; System.Console.WriteLine("Smallest number greater than or equal to " + N +"\nthat is divisible by " + K + " is " + findNum(N, K)); } // This code is contributed by mits} |
PHP
<?php// PHP implementation of the above approach// Function to find the smallest number// greater than or equal to N that is// divisible by kfunction findNum($N, $K){ $rem = ($N + $K) % $K; if ($rem == 0) return $N; else return $N + $K - $rem;}// Driver code$N = 45; $K = 6;echo "Smallest number greater than " . "or equal to ", $N;echo "\nthat is divisible by " , $K , " is " , findNum($N, $K);// This code is contributed by anuj_67?> |
Javascript
<script>// javascript implementation of the above approach// Function to find the smallest number // greater than or equal to N // that is divisible by k function findNum(N , K) { var rem = (N + K) % K; if (rem == 0) return N; else return N + K - rem; } // Driver Code var N = 45, K = 6;document.write("Smallest number greater than or equal to " + N +"<br>that is divisible by " + K + " is " + findNum(N, K));// This code contributed by shikhasingrajput </script> |
Output:
Smallest number greater than or equal to 45 that is divisible by 6 is 48
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!
