Add N digits to A such that it is divisible by B after each addition

0 0 4 minutes read

Given three integers A, B and N, repeat the following process N times:

Add a digit to A such that after adding it, A is divisible by B.
Print the smallest value of A possible after N iterations of above operation.
Print -1 if the operation fails.

Note : We need to check divisibility after every digit addition.
Examples:

Input: A = 10, B = 11, N = 1
Output: -1
No matter what digit you add, 10X will never be divisible by 11.
Input: A = 5, B = 3, N = 3
Output: 5100

Approach: Bruteforce for the first digit to be added from 0 to 9, if none of the digits make A divisible by B then the answer is -1. Otherwise add the first digit that satisfies the condition and then add 0 after that (n-1) times because if A is divisible by B then A*10, A*100, … will also be divisible by B.
Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
int addNDigits(int a, int b, int n)
{
    int num = a;
 
    // Try all digits from (0 to 9)
    for (int i = 0; i <= 9; i++) {
        int tmp = a * 10 + i;
        if (tmp % b == 0) {
            a = tmp;
            break;
        }
    }
 
    // Fails in the first move itself
    if (num == a)
        return -1;
 
    // Add (n-1) 0's
    for (int j = 0; j < n - 1; j++)
        a *= 10;
 
    return a;
}
 
// Driver Program to test above function
int main()
{
    int a = 5, b = 3, n = 3;
    cout << addNDigits(a, b, n);
    return 0;
}

Java

  //Java implementation of the approach
 
import java.io.*;
 
class GFG {
 
 
static int addNDigits(int a, int b, int n)
{
    int num = a;
 
    // Try all digits from (0 to 9)
    for (int i = 0; i <= 9; i++) {
        int tmp = a * 10 + i;
        if (tmp % b == 0) {
            a = tmp;
            break;
        }
    }
 
    // Fails in the first move itself
    if (num == a)
        return -1;
 
    // Add (n-1) 0's
    for (int j = 0; j < n - 1; j++)
        a *= 10;
 
    return a;
}
 
// Driver Program to test above function
 
    public static void main (String[] args) {
    int a = 5, b = 3, n = 3;
    System.out.print( addNDigits(a, b, n));
    }
}
// This code is contributed by anuj_67..

Python3

# Python3 implementation of the approach
def addNDigits(a, b, n) :
 
    num = a
     
    # Try all digits from (0 to 9)
    for i in range(10) :
        tmp = a * 10 + i
         
        if (tmp % b == 0) :
            a = tmp
            break
         
    # Fails in the first move itself
    if (num == a) :
        return -1
 
    # Add (n-1) 0's
    for j in range(n - 1) :
        a *= 10
 
    return a
 
# Driver Code
if __name__ == "__main__" :
     
    a = 5
    b = 3
    n = 3
 
    print(addNDigits(a, b, n))
 
# This code is contributed by Ryuga

C#

// C# implementation of the approach
using System;
 
class GFG 
{
 
static int addNDigits(int a, 
                      int b, int n)
{
    int num = a;
 
    // Try all digits from (0 to 9)
    for (int i = 0; i <= 9; i++)
    {
        int tmp = a * 10 + i;
        if (tmp % b == 0) 
        {
            a = tmp;
            break;
        }
    }
 
    // Fails in the first move itself
    if (num == a)
        return -1;
 
    // Add (n-1) 0's
    for (int j = 0; j < n - 1; j++)
        a *= 10;
 
    return a;
}
 
// Driver Code
public static void Main () 
{
    int a = 5, b = 3, n = 3;
    Console.WriteLine(addNDigits(a, b, n));
}
}
 
// This code is contributed 
// by anuj_67..

PHP

<?php
// PHP implementation of the approach
 
function addNDigits($a, $b, $n)
{
    $num = $a;
 
    // Try all digits from (0 to 9)
    for ($i = 0; $i <= 9; $i++) 
    {
        $tmp = $a * 10 + $i;
        if ($tmp % $b == 0) 
        {
            $a = $tmp;
            break;
        }
    }
 
    // Fails in the first move itself
    if ($num == $a)
        return -1;
 
    // Add (n-1) 0's
    for ($j = 0; $j < $n - 1; $j++)
        $a *= 10;
 
    return $a;
}
 
// Driver Code
$a = 5; $b = 3; $n = 3;
echo addNDigits($a, $b, $n);
 
// This code is contributed
// by Akanksha Rai

Javascript

<script>
    // Javascript implementation of the approach
     
    function addNDigits(a, b, n)
    {
        let num = a;
 
        // Try all digits from (0 to 9)
        for (let i = 0; i <= 9; i++)
        {
            let tmp = a * 10 + i;
            if (tmp % b == 0) 
            {
                a = tmp;
                break;
            }
        }
 
        // Fails in the first move itself
        if (num == a)
            return -1;
 
        // Add (n-1) 0's
        for (let j = 0; j < n - 1; j++)
            a *= 10;
 
        return a;
    }
     
    let a = 5, b = 3, n = 3;
    document.write(addNDigits(a, b, n));
 
</script>

Output:

Time Complexity: O(n)

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!