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 functoolsdef 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 ansdef 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 Codelet 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!
