Dada una array arr[] que consta de N enteros positivos, la tarea es clasificar la array en orden creciente con respecto al número de pasos necesarios para obtener un número de un solo dígito multiplicando sus dígitos recursivamente para cada elemento de la array. Si dos números cualesquiera tienen el mismo número de pasos, imprima primero el número más pequeño.
Ejemplos :
Entrada: arr[] = {39, 999, 4, 9876}
Salida: 4 9876 39 999
Explicación:
Los siguientes son el número de pasos necesarios para reducir cada elemento de la array a 0:
- Para arr[0] (= 39): El elemento 39 se reducirá como 39 → 27 → 14 → 4. Por lo tanto, el número de pasos necesarios es 3.
- Para arr[1] (= 999): El elemento 999 se reducirá como 999 → 729 → 126 → 12 → 2. Por lo tanto, el número de pasos necesarios es 4.
- Para arr[2] (= 4): El elemento 4 ya es un número de un solo dígito. Por lo tanto, el número de pasos necesarios es 0.
- Para arr[3] (= 9876): El elemento 9876 se reducirá como 9876 → 3024 → 0. Por lo tanto, el número de pasos necesarios es 2.
De acuerdo con los criterios dados, los elementos en orden creciente de recuento de pasos necesarios para reducirlos a un número de un solo dígito son {4, 9876, 29, 999}
Entrada: arr[] = {1, 27, 90}
Salida: 1 90 27
Enfoque: El problema dado puede resolverse encontrando el número de pasos necesarios para obtener un número de un solo dígito multiplicando sus dígitos recursivamente para cada elemento de la array y luego ordenando la array en orden creciente usando la función de comparación . Siga los pasos para resolver el problema:
- Declare una función de comparación, cmp(X, Y) que tome dos elementos como parámetro y realice los siguientes pasos:
- Itere un ciclo hasta que X se convierta en un número de un solo dígito y actualice el valor de X al producto de su dígito.
- Repita el paso anterior para el valor Y .
- Si el valor de X es menor que Y , devuelve true . De lo contrario, devuelve falso .
- Ordene la array dada arr[] usando la función de comparación anterior como sort(arr, arr + N, cmp) .
- Después de completar los pasos anteriores, imprima la array arr[] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the number of
// steps required to reduce a given
// number to a single-digit number
int countReduction(int num)
{
// Stores the required result
int ans = 0;
// Iterate until a single digit
// number is not obtained
while (num >= 10) {
// Store the number in a
// temporary variable
int temp = num;
num = 1;
// Iterate over all digits and
// store their product in num
while (temp > 0) {
int digit = temp % 10;
temp = temp / 10;
num *= digit;
}
// Increment the answer
// by 1
ans++;
}
// Return the result
return ans;
}
// Comparator function to sort the array
bool compare(int x, int y)
{
// Count number of steps required
// to reduce X and Y into single
// digits integer
int x1 = countReduction(x);
int y1 = countReduction(y);
// Return true
if (x1 < y1)
return true;
return false;
}
// Function to sort the array according
// to the number of steps required to
// reduce a given number into a single
// digit number
void sortArray(int a[], int n)
{
// Sort the array using the
// comparator function
sort(a, a + n, compare);
// Print the array after sorting
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
}
// Driver Code
int main()
{
int arr[] = { 39, 999, 4, 9876 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
sortArray(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
import java.lang.*;
class GFG
{
// Function to find the number of
// steps required to reduce a given
// number to a single-digit number
static int countReduction(int num)
{
// Stores the required result
int ans = 0;
// Iterate until a single digit
// number is not obtained
while (num >= 10)
{
// Store the number in a
// temporary variable
int temp = num;
num = 1;
// Iterate over all digits and
// store their product in num
while (temp > 0) {
int digit = temp % 10;
temp = temp / 10;
num *= digit;
}
// Increment the answer
// by 1
ans++;
}
// Return the result
return ans;
}
// Function to sort the array according
// to the number of steps required to
// reduce a given number into a single
// digit number
static void sortArray(Integer a[], int n)
{
// Sort the array using the
// comparator function
Arrays.sort(a,new Comparator<Integer>(){
public int compare(Integer x, Integer y)
{
// Count number of steps required
// to reduce X and Y into single
// digits integer
int x1 = countReduction(x);
int y1 = countReduction(y);
// Return true
if (x1 < y1)
return -1;
return 1;
}
});
// Print the array after sorting
for (int i = 0; i < n; i++)
{
System.out.print(a[i] + " ");
}
}
// Driver code
public static void main (String[] args)
{
Integer arr[] = { 39, 999, 4, 9876 };
int N = arr.length;
// Function Call
sortArray(arr, N);
}
}
// This code is contributed by offbeat
Javascript
<script>
// JavaScript program for the above approach
// Function to find the number of
// steps required to reduce a given
// number to a single-digit number
function countReduction(num) {
// Stores the required result
let ans = 0;
// Iterate until a single digit
// number is not obtained
while (num >= 10) {
// Store the number in a
// temporary variable
let temp = num;
num = 1;
// Iterate over all digits and
// store their product in num
while (temp > 0) {
let digit = temp % 10;
temp = Math.floor(temp / 10);
num *= digit;
}
// Increment the answer
// by 1
ans++;
}
// Return the result
return ans;
}
// Comparator function to sort the array
function compare(x, y) {
// Count number of steps required
// to reduce X and Y into single
// digits integer
let x1 = countReduction(x);
let y1 = countReduction(y);
// Return true
if (x1 < y1)
return -1;
return 1;
}
// Function to sort the array according
// to the number of steps required to
// reduce a given number into a single
// digit number
function sortArray(a, n) {
// Sort the array using the
// comparator function
a.sort(compare);
// Print the array after sorting
for (let i = 0; i < n; i++) {
document.write(a[i] + " ");
}
}
// Driver Code
let arr = [39, 999, 4, 9876];
let N = arr.length;
// Function Call
sortArray(arr, N);
</script>
4 9876 39 999
Complejidad de tiempo: O(N * log(N) * log(X)), donde X es el elemento más grande de la array , arr[]
Espacio auxiliar: O(1), ya que no se ha tomado espacio extra.