Smallest number greater than or equal to X whose sum of digits is divisible by Y

0 0 6 minutes read

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 number
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
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
int 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 number
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
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
int 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 Y
 
class GFG{
 
static final 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;
    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 Y
var MAXN = 10000000;
 
// Function that returns the sum
// of digits of a number
function 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 Y
function 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 code
var X = 5923, Y = 13;
document.write(smallestNum(X, Y));
 
 
// This code contributed by shikhasingrajput 
</script>

Output:

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 zambiatek!