#include <iostream>
#include <vector>

// Find the maximum element in the array
int getMax(const std::vector<int>& arr) {
    int max = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] > max)
            max = arr[i];
    }
    return max;
}

// Perform counting sort based on the digit at the given place value
void countingSort(std::vector<int>& arr, int place) {
    const int radix = 10;
    int size = arr.size();

    std::vector<int> count(radix);
    std::vector<int> output(size);

    // Initialize count array
    for (int i = 0; i < radix; i++)
        count[i] = 0;

    // Count the occurrences of each digit
    for (int i = 0; i < size; i++)
        count[(arr[i] / place) % radix]++;

    // Calculate cumulative count
    for (int i = 1; i < radix; i++)
        count[i] += count[i - 1];

    // Build the output array
    for (int i = size - 1; i >= 0; i--) {
        output[count[(arr[i] / place) % radix] - 1] = arr[i];
        count[(arr[i] / place) % radix]--;
    }

    // Copy the output array to arr
    for (int i = 0; i < size; i++)
        arr[i] = output[i];
}

// Perform radix sort
void radixSort(std::vector<int>& arr) {
    int max = getMax(arr);

    // Perform counting sort for each digit, starting from least significant to most significant
    for (int place = 1; max / place > 0; place *= 10)
        countingSort(arr, place);
}

// Function to print the array
void printArray(const std::vector<int>& arr) {
    for (int num : arr)
        std::cout << num << " ";
    std::cout << std::endl;
}

int main() {
    std::vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
    int size = arr.size();

    std::cout << "Original array: ";
    printArray(arr);

    radixSort(arr);

    std::cout << "Sorted array: ";
    printArray(arr);

    return 0;
}