#include<iostream> 
using namespace std; 
 
int getMax(int arr[], int n) 
{ 
    int mx = arr[0]; 
    for (int i = 1; i < n; i++) 
        if (arr[i] > mx) 
            mx = arr[i]; 
    return mx; 
} 
  
void countSort(int arr[], int n, int exp) 
{ 
    int output[n]; 
    int i, count[10] = {0}; 
  
    for (i = 0; i < n; i++) 
        count[ (arr[i]/exp)%10 ]++; 
  
    for (i = 1; i < 10; i++) 
        count[i] += count[i - 1]; 
  
    for (i = n - 1; i >= 0; i--) 
    { 
        output[count[ (arr[i]/exp)%10 ] - 1] = arr[i]; 
        count[ (arr[i]/exp)%10 ]--; 
    } 
  
   
    for (i = 0; i < n; i++) 
        arr[i] = output[i]; 
  for(i=0;i<n;i++) 
  { 
    cout<<arr[i]<<" ";
  }cout<<"\n";
} 
  

void radixsort(int arr[], int n) 
{ 
    int m = getMax(arr, n); 
  
    for (int exp = 1; m/exp > 0; exp *= 10) 
        countSort(arr, n, exp); 

} 
  
void print(int arr[], int n) 
{ 
    for (int i = 0; i < n; i++) 
        cout << arr[i] << " "; 
} 
  
int main() 
{ 
    int n,i,j; 
  int arr[n];
  cin>>n;
  j=n;
  for(i=0;i<n;i++) 
  { 
    cin>>arr[i];
  }
  radixsort(arr, n); 
//aviraj
    return 0; 
} 

Problem Description

Given an array of N integers, you need to print the array after each pass of radix sort. In each pass, you need to sort the array by digits starting from least significant digit to most significant digit.

Input:

The first line consists of an integer N denoting the size of array.
The next line consists of N space separated integers.

Output:

Print the array after each pass. See the output for clarity.

• Test Case 1

  Input (stdin)

  8
  170 45 75 90 802 24 2 66
  

  Expected Output

  170 90 802 2 24 45 75 66 
  802 2 24 45 66 170 75 90 
  2 24 45 66 75 90 170 802

• Test Case 2

  Input (stdin)

  10
  65 47 212 89 177 14 345 68 2 684 
  

  Expected Output

  212 2 14 684 65 345 47 177 68 89 
  2 212 14 345 47 65 68 177 684 89 
  2 14 47 65 68 89 177 212 345 684