Given two integers X and Y, the task is to find the smallest number greater than or equal to X whose sum of digits is divisible by Y.
Note: 1 <= X <= 1000, 1 <= Y <= 50.
Examples:
Input: X = 10, Y = 5
Output: 14
Explanation:
14 is the smallest number greater than 10 whose sum of digits (1+4 = 5) is divisible by 5.
Input: X = 5923, Y = 13
Output: 5939
Approach: The idea for this problem is to run a loop from X and check for each integer if its sum of digits is divisible by Y or not. Return the first number whose sum of digits is divisible by Y. Given the constraints of X and Y, the answer always exist.
Below is the implementation of the above approach:
C++
// C++ program to find the smallest number greater than or// equal to X and divisible by Y#include <bits/stdc++.h>using namespace std;#define MAXN 10000000// Function that returns the sum of digits of a numberint sumOfDigits(int n){ // Initialize variable to store the sum int sum = 0; while (n > 0) { // Add the last digit of the number sum += n % 10; // Remove the last digit from the number n /= 10; } return sum;}// Function that returns the smallest number greater than or// equal to X and divisible by Yint smallestNum(int X, int Y){ // Initialize result variable int res = -1; // Loop through numbers greater than equal to X for (int i = X; i < MAXN; i++) { // Calculate sum of digits int sum_of_digit = sumOfDigits(i); // Check if sum of digits is divisible by Y if (sum_of_digit % Y == 0) { res = i; break; } } return res;}// Driver codeint main(){ int X = 5923, Y = 13; cout << smallestNum(X, Y); return 0;}// This code is contributed by Sania Kumari Gupta |
C
// C program to find the smallest number greater than or// equal to X and divisible by Y#include <stdio.h>#define MAXN 10000000// Function that returns the sum of digits of a numberint sumOfDigits(int n){ // Initialize variable to store the sum int sum = 0; while (n > 0) { // Add the last digit of the number sum += n % 10; // Remove the last digit from the number n /= 10; } return sum;}// Function that returns the smallest number greater than or// equal to X and divisible by Yint smallestNum(int X, int Y){ // Initialize result variable int res = -1; // Loop through numbers greater than equal to X for (int i = X; i < MAXN; i++) { // Calculate sum of digits int sum_of_digit = sumOfDigits(i); // Check if sum of digits is divisible by Y if (sum_of_digit % Y == 0) { res = i; break; } } return res;}// Driver codeint main(){ int X = 5923, Y = 13; printf("%d", smallestNum(X, Y)); return 0;}// This code is contributed by Sania Kumari Gupta |
Java
// Java program to find the smallest number// greater than or equal to X and divisible by Yclass GFG{static final int MAXN = 10000000;// Function that returns the sum// of digits of a numberstatic int sumOfDigits(int n){ // Initialize variable to // store the sum int sum = 0; while (n > 0) { // Add the last digit // of the number sum += n % 10; // Remove the last digit // from the number n /= 10; } return sum;}// Function that returns the smallest number// greater than or equal to X and divisible by Ystatic int smallestNum(int X, int Y){ // Initialize result variable int res = -1; // Loop through numbers greater // than equal to X for (int i = X; i < MAXN; i++) { // Calculate sum of digits int sum_of_digit = sumOfDigits(i); // Check if sum of digits // is divisible by Y if (sum_of_digit % Y == 0) { res = i; break; } } return res;}// Driver codepublic static void main(String[] args){ int X = 5923, Y = 13; System.out.print(smallestNum(X, Y));}}// This code is contributed by Rohit_ranjan |
Python3
# Python3 program to find the smallest number # greater than or equal to X and divisible by Y MAXN = 10000000# Function that returns the # sum of digits of a number def sumOfDigits(n): # Initialize variable # to store the sum sum = 0 while(n > 0): # Add the last digit # of the number sum += n % 10 # Remove the last digit # from the number n //= 10 return sum# Function that returns the smallest number # greater than or equal to X and divisible by Y def smallestNum(X, Y): # Initialize result variable res = -1; # Loop through numbers greater # than equal to X for i in range(X, MAXN): # Calculate sum of digits sum_of_digit = sumOfDigits(i) # Check if sum of digits # is divisible by Y if sum_of_digit % Y == 0: res = i break return res # Driver code if __name__=='__main__': (X, Y) = (5923, 13) print(smallestNum(X, Y))# This code is contributed by rutvik_56 |
C#
// C# program to find the smallest number // greater than or equal to X and divisible by Y using System;class GFG{ static readonly int MAXN = 10000000; // Function that returns the sum // of digits of a number static int sumOfDigits(int n) { // Initialize variable to // store the sum int sum = 0; while(n > 0) { // Add the last digit // of the number sum += n % 10; // Remove the last digit // from the number n /= 10; } return sum; } // Function that returns the smallest number // greater than or equal to X and divisible by Y static int smallestNum(int X, int Y) { // Initialize result variable int res = -1; // Loop through numbers greater // than equal to X for(int i = X; i < MAXN; i++) { // Calculate sum of digits int sum_of_digit = sumOfDigits(i); // Check if sum of digits // is divisible by Y if(sum_of_digit % Y == 0) { res = i; break; } } return res; } // Driver code public static void Main(String[] args) { int X = 5923, Y = 13; Console.Write(smallestNum(X, Y)); } } // This code is contributed by gauravrajput1 |
Javascript
<script>// javascript program to find the smallest number// greater than or equal to X and divisible by Yvar MAXN = 10000000;// Function that returns the sum// of digits of a numberfunction sumOfDigits(n){ // Initialize variable to // store the sum var sum = 0; while (n > 0) { // Add the last digit // of the number sum += n % 10; // Remove the last digit // from the number n = parseInt(n/10); } return sum;}// Function that returns the smallest number// greater than or equal to X and divisible by Yfunction smallestNum(X , Y){ // Initialize result variable var res = -1; // Loop through numbers greater // than equal to X for (i = X; i < MAXN; i++) { // Calculate sum of digits var sum_of_digit = sumOfDigits(i); // Check if sum of digits // is divisible by Y if (sum_of_digit % Y == 0) { res = i; break; } } return res;}// Driver codevar X = 5923, Y = 13;document.write(smallestNum(X, Y));// This code contributed by shikhasingrajput </script> |
Output:
5939
Time Complexity: O(MAXN)
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!
