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 functionint main(){ int a = 5, b = 3, n = 3; cout << addNDigits(a, b, n); return 0;} |
Java
//Java implementation of the approachimport 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 approachdef 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 Codeif __name__ == "__main__" : a = 5 b = 3 n = 3 print(addNDigits(a, b, n))# This code is contributed by Ryuga |
C#
// C# implementation of the approachusing 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 Codepublic 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 approachfunction 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:
5100
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Read More on that Topic: geeksforgeeks.org/add-n-digits-to-a-such-that-it-is-divisible-by-b-after-each-addition/ […]
… [Trackback]
[…] Read More here to that Topic: geeksforgeeks.org/add-n-digits-to-a-such-that-it-is-divisible-by-b-after-each-addition/ […]
… [Trackback]
[…] Read More to that Topic: geeksforgeeks.org/add-n-digits-to-a-such-that-it-is-divisible-by-b-after-each-addition/ […]