Given a number N, the task is to minimize the number by changing at most K digits. Note that the number should not contain any leading zeros.
Examples:
Input: N = 91945, K = 3
Output: 10045
Input: N = 1, K = 0
Output: 1
Approach:
- Replace the first digit with 1 if its not already 1 and update K accordingly.
- Now for the rest of the digits, replace the next K – 1 non-zero digits with a 0.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <iostream>using namespace std;// Function to return the minimized numberstring minNum(string num, int k){ // Total digits in the number int len = num.length(); // If the string is empty or there // are no operations to perform if (len == 0 || k == 0) return num; // "0" is a valid number if (len == 1) return "0"; // If the first digit is not already 1 then // update it to 1 and decrement k if (num[0] != '1') { num[0] = '1'; k--; } int i = 1; // While there are operations left // and the number can still be updated while (k > 0 && i < len) { // If the current digit is not already 0 // then update it to 0 and decrement k if (num[i] != '0') { num[i] = '0'; k--; } i++; } // Return the minimized number return num;}// Driver codeint main(){ string num = "91945"; int k = 3; cout << minNum(num, k); return 0;} |
Java
// Java implementation of the approachimport java.io.*;public class GFG{ // Function to return the minimized number static String minNum(char num[], int k) { // Total digits in the number int len = num.length; // If the string is empty or there // are no operations to perform if (len == 0 || k == 0) { String num_str = new String(num); return num_str; } // "0" is a valid number if (len == 1) return "0"; // If the first digit is not already 1 then // update it to 1 and decrement k if (num[0] != '1') { num[0] = '1'; k--; } int i = 1; // While there are operations left // and the number can still be updated while (k > 0 && i < len) { // If the current digit is not already 0 // then update it to 0 and decrement k if (num[i] != '0') { num[i] = '0'; k--; } i++; } String num_str = new String(num); // Return the minimised number return num_str; } // Driver code public static void main(String args[]) { String num = "91945"; int k = 3; System.out.println(minNum(num.toCharArray(), k)); } }// This code is contributed by AnkitRai01 |
Python3
# Python 3 implementation of the approach # Function to return the minimized number def minNum(num, k) : # Total digits in the number len_ = len(num) # If the string is empty or there # are no operations to perform if len_ == 0 or k == 0 : return num # "0" is a valid number if len_ == 1: return "0" # If the first digit is not already 1 then # update it to 1 and decrement k if num[0] != '1' : num = '1' + num[1:] k -= 1 i = 1 # While there are operations left # and the number can still be updated while k > 0 and i < len_ : # If the current digit is not already 0 # then update it to 0 and decrement k if num[i] != '0' : num = num[:i] + '0' + num[i + 1:] k -= 1 i += 1 # Return the minimised number return num # Driver code num = "91945"k = 3print(minNum(num, k)) # This code is contributed by divyamohan123 |
C#
// C# implementation of the approachusing System; class GFG{ // Function to return the minimized number static String minNum(char []num, int k) { // Total digits in the number int len = num.Length; // If the string is empty or there // are no operations to perform if (len == 0 || k == 0) { return String.Join("", num); } // "0" is a valid number if (len == 1) return "0"; // If the first digit is not already 1 then // update it to 1 and decrement k if (num[0] != '1') { num[0] = '1'; k--; } int i = 1; // While there are operations left // and the number can still be updated while (k > 0 && i < len) { // If the current digit is not already 0 // then update it to 0 and decrement k if (num[i] != '0') { num[i] = '0'; k--; } i++; } // Return the minimised number return String.Join("", num); } // Driver code public static void Main(String []args) { String num = "91945"; int k = 3; Console.WriteLine(minNum(num.ToCharArray(), k)); } }// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approach // Function to return the minimized number function minNum(num, k){ // Total digits in the number let len = num.length; // If the string is empty or there // are no operations to perform if (len == 0 || k == 0) { let num_str = num.join(""); return num_str; } // "0" is a valid number if (len == 1) return "0"; // If the first digit is not already 1 then // update it to 1 and decrement k if (num[0] != '1') { num[0] = '1'; k--; } let i = 1; // While there are operations left // and the number can still be updated while (k > 0 && i < len) { // If the current digit is not already 0 // then update it to 0 and decrement k if (num[i] != '0') { num[i] = '0'; k--; } i++; } let num_str = num.join(""); // Return the minimised number return num_str;}// Driver code let num = "91945";let k = 3;document.write(minNum(num.split(""), k));// This code is contributed by _saurabh_jaiswal.</script> |
Output:
10045
Time Complexity: O(min(k, |num|))
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!
