Minimize the number by changing at most K digits

0 0 4 minutes read

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 number
string 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 code
int main()
{
    string num = "91945";
    int k = 3;
 
    cout << minNum(num, k);
 
    return 0;
}

Java

// Java implementation of the approach
import 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 = 3
 
print(minNum(num, k)) 
 
# This code is contributed by divyamohan123

C#

// C# implementation of the approach
using 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:

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