Given an array arr of size N, the task is to sort the digits of each element in the array and then sort the array in non-decreasing order. Print the array after sorting.
Examples:
Input: arr[] = {514, 34, 41, 39}
Output: 41 43 93 541
Explanation:
Sorting each element of the array: arr[] = {145, 34, 14, 39}
Sorting the array: arr[] = {14, 34, 39, 145}Input: arr[] = {3, 1, 9, 4}
Output: 1 3 4 9
Approach: Follow the steps below to solve this problem:
- Create a function toString, which will accept the integer N as an parameter and will return N the form of string.
- Pass each element of array arr in function toString to convert it to string. Sort that string and convert it back to an integer. After this, replace each element with the converted integer in array arr.
- Sort the array arr and print the answer according to the above observation.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to print array in non-decreasing ordervoid printArray(int arr[], int N){ for (int i = 0; i < N; i++) cout << arr[i] << " ";}// Function to convert an integer to stringstring toString(int N){ string s; while (N > 0) { s += (N % 10) + '0'; N /= 10; } if (s.size() == 0) { s = "0"; } return s;}// Function to sort each element of the array// in non-descreasing order of its digitsvoid digitSort(int arr[], int N){ // Traversing each element to sort for (int i = 0; i < N; i++) { // Converting number to string string s = toString(arr[i]); // Sorting string sort(s.begin(), s.end()); // Converting string to integer arr[i] = stoi(s); } // Sorting array sort(arr, arr + N); // Printing array printArray(arr, N);}// Driver Codeint main(){ int arr[] = { 514, 34, 41, 39 }; int N = sizeof(arr) / sizeof(arr[0]); digitSort(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to print array in non-decreasing orderstatic void printArray(int arr[], int N){ for (int i = 0; i < N; i++) System.out.print(arr[i] + " ");}// Function to convert an integer to Stringstatic String toString(int N){ String s = ""; while (N > 0) { s += String.valueOf((N % 10)) + '0'; N /= 10; } if (s.length() == 0) { s = "0"; } return s;}// Function to sort each element of the array// in non-descreasing order of its digitsstatic void digitSort(int arr[], int N){ // Traversing each element to sort for (int i = 0; i < N; i++) { // Converting number to String String s = toString(arr[i]); // Sorting String s = sort(s); // Converting String to integer arr[i] = Integer.valueOf(s); } // Sorting array Arrays.sort(arr); // Printing array printArray(arr, N);}static String sort(String inputString) { // convert input string to char array char tempArray[] = inputString.toCharArray(); // sort tempArray Arrays.sort(tempArray); // return new sorted string return new String(tempArray); } // Driver Codepublic static void main(String[] args){ int arr[] = { 514, 34, 41, 39 }; int N = arr.length; digitSort(arr, N);}}// This code is contributed by shikhasingrajput |
Python3
# python program for the above approach# Function to print array in non-decreasing orderdef printArray(arr, N): for i in range(0, N): print(arr[i], end=" ")# Function to convert an integer to stringdef toString(N): s = "" while (N > 0): s += chr(int(N % 10) + ord('0')) N /= 10 if (len(s) == 0): s = "0" return s# Function to sort each element of the array# in non-descreasing order of its digitsdef digitSort(arr, N): # Traversing each element to sort for i in range(0, N): # Converting number to string s = toString(arr[i]) # Sorting string s = list(s) s.sort() s = ''.join(s) # Converting string to integer arr[i] = int(s) # Sorting array arr.sort() # Printing array printArray(arr, N)# Driver Codeif __name__ == "__main__": arr = [514, 34, 41, 39] N = len(arr) digitSort(arr, N) # This code is contributed by rakeshsahni |
C#
// Java program for the above approachusing System;using System.Collections;class GFG{ // Function to print array in non-decreasing orderstatic void printArray(int []arr, int N){ for (int i = 0; i < N; i++) Console.Write(arr[i] + " ");}// Function to convert an integer to stringstatic String toString(int N){ string s = ""; while (N > 0) { int val = N % 10; s += val.ToString(); N /= 10; } if (s.Length == 0) { s = "0"; } return s;}// Function to sort each element of the array// in non-descreasing order of its digitsstatic void digitSort(int []arr, int N){ int []ans = new int[N]; // Traversing each element to sort for (int i = 0; i < N; i++) { // Converting number to string String s = toString(arr[i]); char []ch = s.ToCharArray(); Array.Sort(ch); ans[i] = Int32.Parse(String.Join("",ch)); // Converting string to integer arr[i] = Int32.Parse(s); } // Sorting array Array.Sort(ans); // Printing array printArray(ans, N);}// Driver Codepublic static void Main(){ int []arr = { 514, 34, 41, 39 }; int N = arr.Length; digitSort(arr, N);}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// JavaScript program for the above approach // Function to print array in // non-decreasing orderfunction printArray(arr, N){ for(let i = 0; i < N; i++) document.write(arr[i] + " ");}// Function to convert an integer to stringfunction toString(N){ let s = ""; while (N > 0) { s = s + (N % 10).toString(); N = Math.floor(N / 10); } if (s.length == 0) { s = "0"; } return s;}// Function to sort each element of the array// in non-descreasing order of its digitsfunction digitSort(arr, N) { // Traversing each element to sort for(let i = 0; i < N; i++) { // Converting number to string let s = arr[i].toString(); // Sorting string st = s.split('') st.sort(function (a, b){ return a.charCodeAt(0) - b.charCodeAt(0); }); s = ''; for(let i = 0; i < st.length; i++) { s = s + st[i]; } // Converting string to integer arr[i] = parseInt(s); } // Sorting array arr.sort(function(a, b){ return a - b }) // Printing array printArray(arr, N);}// Driver Codelet arr = [ 514, 34, 41, 39 ];let N = arr.length;digitSort(arr, N);// This code is contributed by Potta Lokesh</script> |
Output
14 34 39 145
Time Complexity: O(N log N), the inbuilt sort function takes N log N time.
Auxiliary space: O(1), since constant extra space is used.
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!
