Sort an array in increasing order of their Multiplicative Persistence

0 0 7 minutes read

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 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

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 Call
SortArray(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 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>

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 zambiatek!