Eliminaciones mínimas en un número para ser divisible por 10 potencia elevada a K

Posted on by Rudeus Greyrat

Dados dos enteros positivos N y K . Encuentre el número mínimo de dígitos que se pueden quitar del número N tal que después de quitar el número sea divisible por 10 K o imprima -1 si es imposible.
Ejemplos: 
 

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

Enfoque: La idea es comenzar a recorrer el número desde el último dígito mientras se mantiene un contador. Si el dígito actual no es cero, incremente la variable del contador; de lo contrario, disminuya la variable K. Cuando K sea cero, devuelva el contador como respuesta. Después de recorrer el número entero, verifique si el valor actual de K es cero o no. Si es cero, devuelve el contador como respuesta; de lo contrario, devuelve la respuesta como un número de dígitos en N – 1, ya que necesitamos reducir el número entero a un solo cero que es divisible por cualquier número. Además, si el número dado no contiene ningún cero, devuelva -1 como respuesta.
A continuación se muestra la implementación del enfoque anterior. 
 

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 removed
int 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 function
int 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 removed
def 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 Code
N = 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 removed
function 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>
Producción: 

3
3
-1

 

Complejidad del tiempo: Número de dígitos en el número dado.
 

Publicación traducida automáticamente

Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *