Dado un número 
. Reduzca este número a cero restando el número por su dígito más significativo (el dígito más a la izquierda) en cada paso. La tarea es contar el número de pasos que se necesitan para reducirse a cero.
Ejemplos :
Input: 14 Output: 6 Steps: 14 - 1 = 13 13 - 1 = 12 12 - 1 = 11 11 - 1 = 10 10 - 1 = 9 9 - 9 = 0 Input: 20 Output: 12 Numbers after series of steps: 20, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 0
Enfoque ingenuo : un enfoque ingenuo es reducir el número por su primer dígito paso a paso y encontrar el conteo de pasos, pero la complejidad del tiempo será enorme si se proporciona un número grande.
Enfoque eficiente: la idea principal del enfoque eficiente es reducir el número de pasos en el enfoque ingenuo. Podemos omitir los pasos cuyos primeros dígitos son los mismos en números consecutivos y contarlos. El algoritmo de omitir esos números con los mismos dígitos iniciales es el siguiente:
- Deje que el número sea el último, cuente los dígitos al final y redúzcalo en 1, porque el número más pequeño con el mismo dígito inicial con el mismo número de dígitos tendrá ese número de ceros.
- Encuentre el primer dígito del número del último, por último/recuento.
- Por lo tanto, el número más pequeño del mismo número de recuento de dígitos con el mismo número inicial será [primer dígito * (recuento-1)]
- el número de pasos omitidos se puede lograr mediante [(último número más pequeño)/primer dígito] .
- Por lo tanto, el siguiente número será el último – (primero*omitido)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the count of Steps to
// reduce N to zero by subtracting its most
// significant digit at every step
#include <bits/stdc++.h>
using namespace std;
// Function to count the number
// of digits in a number m
int countdig(int m)
{
if (m == 0)
return 0;
else
return 1 + countdig(m / 10);
}
// Function to count the number of
// steps to reach 0
int countSteps(int x)
{
// count the total number of steps
int c = 0;
int last = x;
// iterate till we reach 0
while (last) {
// count the digits in last
int digits = countdig(last);
// decrease it by 1
digits -= 1;
// find the number on whose division,
// we get the first digit
int divisor = pow(10, digits);
// first digit in last
int first = last / divisor;
// find the first number less than
// last where the first digit changes
int lastnumber = first * divisor;
// find the number of numbers
// with same first digit that are jumped
int skipped = (last - lastnumber) / first;
skipped += 1;
// count the steps
c += skipped;
// the next number with a different
// first digit
last = last - (first * skipped);
}
return c;
}
// Driver code
int main()
{
int n = 14;
cout << countSteps(n);
return 0;
}
Java
// Java program to find the count of Steps to
// reduce N to zero by subtracting its most
// significant digit at every step
class GFG{
// Function to count the number
// of digits in a number m
static int countdig(int m)
{
if (m == 0)
return 0;
else
return 1 + countdig(m / 10);
}
// Function to count the number of
// steps to reach 0
static int countSteps(int x)
{
// count the total number of steps
int c = 0;
int last = x;
// iterate till we reach 0
while (last>0) {
// count the digits in last
int digits = countdig(last);
// decrease it by 1
digits -= 1;
// find the number on whose division,
// we get the first digit
int divisor = (int)Math.pow(10, digits);
// first digit in last
int first = last / divisor;
// find the first number less than
// last where the first digit changes
int lastnumber = first * divisor;
// find the number of numbers
// with same first digit that are jumped
int skipped = (last - lastnumber) / first;
skipped += 1;
// count the steps
c += skipped;
// the next number with a different
// first digit
last = last - (first * skipped);
}
return c;
}
// Driver code
public static void main(String[] args)
{
int n = 14;
System.out.println(countSteps(n));
}
}
// This code is contributed by mits
Python 3
# Python 3 program to find the # count of Steps to reduce N to # zero by subtracting its most # significant digit at every step # Function to count the number # of digits in a number m def countdig(m) : if (m == 0) : return 0 else : return 1 + countdig(m // 10) # Function to count the number # of steps to reach 0 def countSteps(x) : # count the total number # of steps c = 0 last = x # iterate till we reach 0 while (last) : # count the digits in last digits = countdig(last) # decrease it by 1 digits -= 1 # find the number on whose # division, we get the first digit divisor = pow(10, digits) # first digit in last first = last // divisor # find the first number less # than last where the first # digit changes lastnumber = first * divisor # find the number of numbers # with same first digit that # are jumped skipped = (last - lastnumber) // first skipped += 1 # count the steps c += skipped # the next number with a different # first digit last = last - (first * skipped) return c # Driver code n = 14 print(countSteps(n)) # This code is contributed by ANKITRAI1
C#
// C# program to find the count of Steps to
// reduce N to zero by subtracting its most
// significant digit at every step
using System;
class GFG{
// Function to count the number
// of digits in a number m
static int countdig(int m)
{
if (m == 0)
return 0;
else
return 1 + countdig(m / 10);
}
// Function to count the number of
// steps to reach 0
static int countSteps(int x)
{
// count the total number of steps
int c = 0;
int last = x;
// iterate till we reach 0
while (last>0) {
// count the digits in last
int digits = countdig(last);
// decrease it by 1
digits -= 1;
// find the number on whose division,
// we get the first digit
int divisor = (int)Math.Pow(10, digits);
// first digit in last
int first = last / divisor;
// find the first number less than
// last where the first digit changes
int lastnumber = first * divisor;
// find the number of numbers
// with same first digit that are jumped
int skipped = (last - lastnumber) / first;
skipped += 1;
// count the steps
c += skipped;
// the next number with a different
// first digit
last = last - (first * skipped);
}
return c;
}
// Driver code
static void Main()
{
int n = 14;
Console.WriteLine(countSteps(n));
}
}
// This code is contributed by mits
PHP
<?php
// PHP program to find the count of Steps to
// reduce N to zero by subtracting its most
// significant digit at every step
// Function to count the number
// of digits in a number m
function countdig($m)
{
if ($m == 0)
return 0;
else
return 1 + countdig( (int)($m / 10));
}
// Function to count the number of
// steps to reach 0
function countSteps($x)
{
// count the total number of steps
$c = 0;
$last = $x;
// iterate till we reach 0
while ($last)
{
// count the digits in last
$digits = countdig($last);
// decrease it by 1
$digits -= 1;
// find the number on whose division,
// we get the first digit
$divisor = pow(10, $digits);
// first digit in last
$first = (int)($last / $divisor);
// find the first number less than
// last where the first digit changes
$lastnumber = $first * $divisor;
// find the number of numbers
// with same first digit that are jumped
$skipped = ($last - $lastnumber) / $first;
$skipped += 1;
// count the steps
$c += $skipped;
// the next number with a different
// first digit
$last = $last - ($first * $skipped);
}
return $c;
}
// Driver code
$n = 14;
echo countSteps($n);
// This code is contributed
// by Akanksha Rai
Javascript
<script>
// javascript program to find the count of Steps to
// reduce N to zero by subtracting its most
// significant digit at every step
// Function to count the number
// of digits in a number m
function countdig(m) {
if (m == 0)
return 0;
else
return 1 + countdig(parseInt(m / 10));
}
// Function to count the number of
// steps to reach 0
function countSteps(x) {
// count the total number of steps
var c =0;
var last = x;
// iterate till we reach 0
while (last > 0) {
// count the digits in last
var digits = countdig(last);
// decrease it by 1
digits -= 1;
// find the number on whose division,
// we get the first digit
var divisor = parseInt( Math.pow(10, digits));
// first digit in last
var first = parseInt(last / divisor);
// find the first number less than
// last where the first digit changes
var lastnumber = first * divisor;
// find the number of numbers
// with same first digit that are jumped
var skipped = parseInt((last - lastnumber) / first);
skipped += 1;
// count the steps
c += skipped;
// the next number with a different
// first digit
last = last - (first * skipped);
}
return c;
}
// Driver code
var n = 14;
document.write(countSteps(n));
// This code is contributed by todaysgaurav
</script>
Producción:
6
Complejidad de tiempo: O(N*logN), ya que en el peor de los casos, el bucle while atravesará N veces y en cada recorrido estamos usando la función de potencia y la función de conteo, cada una de estas costará un tiempo de registro, por lo que la complejidad de tiempo efectiva del programa será O (N*logN).
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.