Given an array arr[] consisting of N positive integers, the task is to sort the array in increasing order with respect to the count of steps required to obtain a single-digit number by multiplying its digits recursively for each array element. If any two numbers have the same count of steps, then print the smaller number first.
Examples:
Input: arr[] = {39, 999, 4, 9876}Â
Output: 4 9876 39 999Â
Explanation:
Following are the number of steps required to reduce every array element to 0:
- For arr[0] (= 39): The element 39 will reduce as 39 ? 27 ? 14 ? 4. Therefore, the number of steps required is 3.
- For arr[1] (= 999): The element 999 will reduce as 999 ? 729 ? 126 ? 12 ? 2. Therefore, the number of steps required is 4.
- For arr[2] (= 4): The element 4 is already a single-digit number. Therefore, the number of steps required is 0.
- For arr[3] (= 9876): The element 9876 will reduce as 9876 ? 3024 ? 0. Therefore, the number of steps required is 2.
According to the given criteria the elements in increasing order of count of steps required to reduce them into single-digit number is {4, 9876, 29, 999}
Input: arr[] = {1, 27, 90}Â
Output: 1Â 90 27Â
Approach: The given problem can be solved by finding the count of steps required to obtain a single-digit number by multiplying its digits recursively for each array element and then sort the array in increasing order using the comparator function. Follow the steps to solve the problem:
- Declare a comparator function, cmp(X, Y) that takes two elements as a parameter and perform the following steps:
- Iterate a loop until X becomes a single-digit number and update the value of X to the product of its digit.
- Repeat the above step for the value Y.
- If the value of X is less than Y, then return true. Otherwise, return false.
- Sort the given array arr[] by using the above comparator function as sort(arr, arr + N, cmp).
- After completing the above steps, print the array arr[].
Below is the implementation of the above approach:
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 numberint 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 arraybool 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 numbervoid 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 Codeint 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 approachimport java.util.*;import java.lang.*;class GFG {Â
// Function to find the number of// steps required to reduce a given// number to a single-digit numberstatic 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 numberstatic 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 codepublic 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 |
Python3
import functoolsÂ
def CountReduction(num):    # Stores the required result    ans = 0Â
    # Iterate until a single digit    # number is not obtained    while num >= 10:        # Store the number in a        # temporary variable        temp = num        num = 1Â
        # Iterate over all digits and        # store their product in num        while temp > 0:            digit = temp % 10            temp = temp // 10            num *= digitÂ
        # Increment the answer        # by 1        ans += 1Â
    # Return the result    return ansÂ
def SortArray(a):    # Sort the array using the    # comparator function    a.sort(key=CountReduction)Â
    # Print the array after sorting    print(a)Â
arr = [39, 999, 4, 9876]Â
# Function CallSortArray(arr)Â
# This code is provided by mukul ojha |
C#
using System;using System.Linq;Â
class Program{  // 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(int[] a, int n)  {    // Sort the array using the    // comparator function    Array.Sort(a, (x, 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    Console.WriteLine(string.Join(" ", a.Select(x => x.ToString())));  }Â
  static void Main(string[] args)  {    int[] arr = { 39, 999, 4, 9876 };    int N = arr.Length;Â
    // Function Call    SortArray(arr, N);  }}Â
// This code is contributed by aadityaburujwale. |
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 numberfunction 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 arrayfunction 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 numberfunction 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 CallsortArray(arr, N);Â
</script> |
Output:Â
4 9876 39 999
Â
Time Complexity: O(N * log(N) * log(X)), where X is the largest element in the array, arr[]
Auxiliary Space: O(1), Â since no extra space has been taken.
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!
