Given two positive integers N and K. Find the minimum number of digits that can be removed from the number N such that after removals the number is divisible by 10K or print -1 if it is impossible.
Examples:
Input : N = 10904025, K = 2 Output : 3 Explanation : We can remove the digits 4, 2 and 5 such that the number becomes 10900 which is divisible by 102. Input : N = 1000, K = 5 Output : 3 Explanation : We can remove the digits 1 and any two zeroes such that the number becomes 0 which is divisible by 105 Input : N = 23985, K = 2 Output : -1
Approach : The idea is to start traversing the number from the last digit while keeping a counter. If the current digit is not zero, increment the counter variable, otherwise decrement variable K. When K becomes zero, return counter as answer. After traversing the whole number, check if the current value of K is zero or not. If it is zero, return counter as answer, otherwise return answer as number of digits in N – 1, since we need to reduce the whole number to a single zero which is divisible by any number. Also, if the given number does not contain any zero, return -1 as answer.
Below is the implementation of above approach.
C++
// CPP Program to count the number// of digits that can be removed such// that number is divisible by 10^K#include <bits/stdc++.h>using namespace std;// function to return the required// number of digits to be removedint countDigitsToBeRemoved(int N, int K){ // Converting the given number // into string string s = to_string(N); // variable to store number of // digits to be removed int res = 0; // variable to denote if atleast // one zero has been found int f_zero = 0; for (int i = s.size() - 1; i >= 0; i--) { if (K == 0) return res; if (s[i] == '0') { // zero found f_zero = 1; K--; } else res++; } // return size - 1 if K is not zero and // atleast one zero is present, otherwise // result if (!K) return res; else if (f_zero) return s.size() - 1; return -1;}// Driver Code to test above functionint main(){ int N = 10904025, K = 2; cout << countDigitsToBeRemoved(N, K) << endl; N = 1000, K = 5; cout << countDigitsToBeRemoved(N, K) << endl; N = 23985, K = 2; cout << countDigitsToBeRemoved(N, K) << endl; return 0;} |
Java
// Java Program to count the number // of digits that can be removed such // that number is divisible by 10^K public class GFG{ // function to return the required // number of digits to be removed static int countDigitsToBeRemoved(int N, int K) { // Converting the given number // into string String s = Integer.toString(N); // variable to store number of // digits to be removed int res = 0; // variable to denote if atleast // one zero has been found int f_zero = 0; for (int i = s.length() - 1; i >= 0; i--) { if (K == 0) return res; if (s.charAt(i) == '0') { // zero found f_zero = 1; K--; } else res++; } // return size - 1 if K is not zero and // atleast one zero is present, otherwise // result if (K == 0) return res; else if (f_zero == 1) return s.length() - 1; return -1; } // Driver Code to test above function public static void main(String []args) { int N = 10904025; int K = 2; System.out.println(countDigitsToBeRemoved(N, K)) ; N = 1000 ; K = 5; System.out.println(countDigitsToBeRemoved(N, K)) ; N = 23985; K = 2; System.out.println(countDigitsToBeRemoved(N, K)) ; } // This code is contributed by Ryuga } |
Python3
# Python3 Program to count the number# of digits that can be removed such# that number is divisible by 10^K# function to return the required# number of digits to be removeddef countDigitsToBeRemoved(N, K): # Converting the given number # into string s = str(N); # variable to store number of # digits to be removed res = 0; # variable to denote if atleast # one zero has been found f_zero = 0; for i in range(len(s) - 1, -1, -1): if (K == 0): return res; if (s[i] == '0'): # zero found f_zero = 1; K -= 1; else: res += 1; # return size - 1 if K is not zero and # atleast one zero is present, otherwise # result if (K == 0): return res; elif (f_zero > 0): return len(s) - 1; return -1;# Driver CodeN = 10904025;K = 2;print(countDigitsToBeRemoved(N, K));N = 1000;K = 5;print(countDigitsToBeRemoved(N, K));N = 23985;K = 2;print(countDigitsToBeRemoved(N, K)); # This code is contributed by mits |
C#
// C# Program to count the number // of digits that can be removed such // that number is divisible by 10^K using System;public class GFG{ // function to return the required // number of digits to be removed static int countDigitsToBeRemoved(int N, int K) { // Converting the given number // into string string s = Convert.ToString(N); // variable to store number of // digits to be removed int res = 0; // variable to denote if atleast // one zero has been found int f_zero = 0; for (int i = s.Length - 1; i >= 0; i--) { if (K == 0) return res; if (s[i] == '0') { // zero found f_zero = 1; K--; } else res++; } // return size - 1 if K is not zero and // atleast one zero is present, otherwise // result if (K == 0) return res; else if (f_zero == 1) return s.Length - 1; return -1; } // Driver Code to test above function public static void Main() { int N = 10904025; int K = 2; Console.Write(countDigitsToBeRemoved(N, K)+"\n") ; N = 1000 ; K = 5; Console.Write(countDigitsToBeRemoved(N, K)+"\n") ; N = 23985; K = 2; Console.Write(countDigitsToBeRemoved(N, K)+"\n") ; } } |
PHP
<?php// PHP Program to count the number// of digits that can be removed such// that number is divisible by 10^K// function to return the required// number of digits to be removedfunction countDigitsToBeRemoved($N, $K){ // Converting the given number // into string $s = strval($N); // variable to store number of // digits to be removed $res = 0; // variable to denote if atleast // one zero has been found $f_zero = 0; for ($i = strlen($s)-1; $i >= 0; $i--) { if ($K == 0) return $res; if ($s[$i] == '0') { // zero found $f_zero = 1; $K--; } else $res++; } // return size - 1 if K is not zero and // atleast one zero is present, otherwise // result if (!$K) return $res; else if ($f_zero) return strlen($s) - 1; return -1;}// Driver Code to test above function $N = 10904025; $K = 2; echo countDigitsToBeRemoved($N, $K)."\n"; $N = 1000; $K = 5; echo countDigitsToBeRemoved($N, $K)."\n"; $N = 23985; $K = 2; echo countDigitsToBeRemoved($N, $K); // This code is contributed by mits?> |
Javascript
<script> // JavaScript Program to count the number // of digits that can be removed such // that number is divisible by 10^K // Function to return the required // number of digits to be removed function countDigitsToBeRemoved(N, K) { // Converting the given number // into string var s = N.toString(); // variable to store number of // digits to be removed var res = 0; // variable to denote if atleast // one zero has been found var f_zero = 0; for (var i = s.length - 1; i >= 0; i--) { if (K === 0) return res; if (s[i] === "0") { // zero found f_zero = 1; K--; } else res++; } // return size - 1 if K is not zero and // atleast one zero is present, otherwise // result if (K === 0) return res; else if (f_zero === 1) return s.length - 1; return -1; } // Driver Code to test above function var N = 10904025; var K = 2; document.write(countDigitsToBeRemoved(N, K) + "<br>"); N = 1000; K = 5; document.write(countDigitsToBeRemoved(N, K) + "<br>"); N = 23985; K = 2; document.write(countDigitsToBeRemoved(N, K) + "<br>"); </script> |
Output:
3 3 -1
Time Complexity : O(n) where n is number of digits in the given number.
Auxiliary Space: O(n)
Example in c:
Approach:
We count the number of trailing zeros in the given number by checking the remainder of the number when divided by 10^k.
If the number of trailing zeros is less than k, then it is not possible to make the number divisible by 10^k by removing digits. So, we return -1.
Otherwise, we count the number of digits that need to be removed to make the number divisible by 10^k. This is done by counting the number of non-zero digits in the number from the right end until we have removed k digits.
C++
// C++ code addition #include <bits/stdc++.h>using namespace std;// function to count the number of removals required to make a number divisible by 10^kint countRemovals(int n, int k) { int count = 0; while (n > 0 && k > 0) { if (n % 10 == 0) { k--; } else { count++; } n /= 10; } if (k > 0) { return -1; } else { return count; }}int main() { int n = 432150, k = 3; int result = countRemovals(n, k); if (result == -1) { cout << "It is not possible to make the number divisible by 10^" << k << endl; } else { cout << "The minimum number of removals required to make the number divisible by 10" << k << " is 10^" << result << endl; } return 0;}// The code is contributed by Anjali goel. |
C
#include <stdio.h>// function to count the number of removals required to make a number divisible by 10^kint countRemovals(int n, int k) { int count = 0; while (n > 0 && k > 0) { if (n % 10 == 0) { k--; } else { count++; } n /= 10; } if (k > 0) { return -1; } else { return count; }}int main() { int n = 432150, k = 3; int result = countRemovals(n, k); if (result == -1) { printf("It is not possible to make the number divisible by 10^%d\n", k); } else { printf("The minimum number of removals required to make the number divisible by 10^%d is %d\n", k, result); } return 0;} |
Java
// Java program for the above approachimport java.util.Scanner;public class Main { // function to count the number of removals required to // make a number divisible by 10^k static int countRemovals(int n, int k) { int count = 0; while (n > 0 && k > 0) { if (n % 10 == 0) { k--; } else { count++; } n /= 10; } if (k > 0) { return -1; } else { return count; } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = 432150, k = 3; int result = countRemovals(n, k); if (result == -1) { System.out.printf( "It is not possible to make the number divisible by 10^%d\n", k); } else { System.out.printf( "The minimum number of removals required to make the number divisible by 10^%d is %d\n", k, result); } scanner.close(); }}// Contributed by adityasha4x71 |
Python3
# Python program for the above approachdef countRemovals(n, k): count = 0 while n > 0 and k > 0: if n % 10 == 0: k -= 1 else: count += 1 n //= 10 if k > 0: return -1 else: return countn = 432150k = 3result = countRemovals(n, k)if result == -1: print("It is not possible to make the number divisible by 10^", k)else: print("The minimum number of removals required to make the number divisible by 10^", k, "is", result) |
C#
using System;public class MainClass { // function to count the number of removals required to // make a number divisible by 10^k static int countRemovals(int n, int k) { int count = 0; while (n > 0 && k > 0) { if (n % 10 == 0) { k--; } else { count++; } n /= 10; } if (k > 0) { return -1; } else { return count; } } public static void Main(string[] args) { int n = 432150, k = 3; int result = countRemovals(n, k); if (result == -1) { Console.WriteLine( "It is not possible to make the number divisible by 10^{0}", k); } else { Console.WriteLine( "The minimum number of removals required to make the number divisible by 10^{0} is {1}", k, result); } }} |
Javascript
// JavaScript program for the above approachfunction countRemovals(n, k) {let count = 0;while (n > 0 && k > 0) {if (n % 10 === 0) {k -= 1;} else {count += 1;}n = Math.floor(n / 10);}if (k > 0) {return -1;} else {return count;}}let n = 432150;let k = 3;let result = countRemovals(n, k);if (result === -1) {console.log("It is not possible to make the number divisible by 10^", k);} else {console.log("The minimum number of removals required to make the number divisible by 10^",k,"is",result);} |
Output
It is not possible to make the number divisible by 10^3
Time complexity: O(log n), where n is the given number.
Auxiliary Space: O(1), as we are not using any additional data structures.
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!
