import java.util.*;

public class RadixSort {

// A utility function to get maximum value in arr[]

static int getMax(int arr[], int n)

{

int mx = arr[0];

for (int i = 1; i

if (arr[i] > mx)

mx = arr[i];

return mx;

}

// A function to do counting sort of arr[] according to

// the digit represented by exp.

static void countSort(int arr[], int n, int exp)

{

int output[] = new int[n]; // output array

int i;

int count[] = new int[10];

Arrays.fill(count,0);

// Store count of occurrences in count[]

for (i = 0; i

int key = (arr[i] / exp) % 10;

if(key%2 == 1) {

System.out.println("Key containing odd digits");

System.exit(0);

}

count[key]++;

}

// Change count[i] so that count[i] now contains

// actual position of this digit in output[]

for (i = 1; i

count[i] += count[i - 1];

// Build the output array

for (i = n - 1; i >= 0; i--)

{

output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];

count[ (arr[i]/exp)%10 ]--;

}

// Copy the output array to arr[], so that arr[] now

// contains sorted numbers according to curent digit

for (i = 0; i

arr[i] = output[i];

}

// The main function to that sorts arr[] of size n using

// Radix Sort

static void radixsort(int arr[], int n)

{

// Find the maximum number to know number of digits

int m = getMax(arr, n);

// Do counting sort for every digit. Note that instead

// of passing digit number, exp is passed. exp is 10^i

// where i is current digit number

for (int exp = 1; m/exp > 0; exp *= 10)

countSort(arr, n, exp);

}

// A utility function to print an array

static void print(int arr[], int n)

{

for (int i=0; i

System.out.print(arr[i]+" ");

}

/*Driver function to check for above function*/

public static void main (String[] args)

{

int arr[] = {420, 44, 42, 60, 802, 24, 2, 66};

int n = arr.length;

radixsort(arr, n);

print(arr, n);

}

}

(b) What is the running time complexity of your radixSort method? Justify