Problem: Finding the K-th Smallest Number

Given an array of n integers (n < 5,000,000, odd) and an integer k, find the k-th smallest element where the smallest element is considered the 0-th.

Initial Approach with Standard Sort

An initial solution using standard sorting:

#include<iostream>
#include<algorithm>
using namespace std;

const int MAX_SIZE = 5000001;
int arr[MAX_SIZE];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> arr[i];
    sort(arr, arr + n);
    cout << arr[k];
    return 0;
}

This approach works but fails on larger test cases due to O(n log n) time complexity.

Optimized Approach Using Quickselect

A more efficient solution implements the quickselect algorithm:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int data[5000005];
int targetIndex;

void quickSelect(int left, int right) {
    int i = left, j = right;
    int pivot = data[(left + right) / 2];
    
    do {
        while (data[i] < pivot) i++;
        while (data[j] > pivot) j--;
        if (i <= j) {
            swap(data[i], data[j]);
            i++;
            j--;
        }
    } while (i <= j);
    
    if (targetIndex <= j) quickSelect(left, j);
    else if (i <= targetIndex) quickSelect(i, right);
    else {
        printf("%d", data[j+1]);
        exit(0);
    }
}

int main() {
    int n;
    scanf("%d%d", &n, &targetIndex);
    for (int i = 0; i < n; i++) scanf("%d", &data[i]);
    quickSelect(0, n-1);
    return 0;
}

This O(n) average case solution passes all test cases.

Alternative Solution Using STL nth_element

The STL provides a built-in solution:

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

int numbers[5000005];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &numbers[i]);
    nth_element(numbers, numbers + k, numbers + n);
    printf("%d", numbers[k]);
    return 0;
}

Problem: Removing Duplicates and Sorting

Given N random integers (1 ≤ N ≤ 100) between 1 and 1000, remove duplicates and output the sorted unique values.

Solution Using Cuonting Sort

#include<iostream>
using namespace std;

int counter[1001] = {0};

int main() {
    int n, value;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        cin >> value;
        counter[value]++;
    }
    
    int count = 0;
    for (int i = 1; i <= 1000; i++) {
        if (counter[i] > 0) count++;
    }
    
    cout << count << endl;
    for (int i = 1; i <= 1000; i++) {
        if (counter[i] > 0) cout << i << " ";
    }
    
    return 0;
}

Problem: Finding the Maximum Number

Given n large numbers (up to 100 digits), find the largest number and its position.

Solution Using String Comparison

#include<iostream>
#include<string>
using namespace std;

int main() {
    int n;
    cin >> n;
    string maxNum = "";
    int maxIndex = 0;
    
    for (int i = 0; i < n; i++) {
        string num;
        cin >> num;
        if (num.length() > maxNum.length() || 
            (num.length() == maxNum.length() && num > maxNum)) {
            maxNum = num;
            maxIndex = i + 1;
        }
    }
    
    cout << maxIndex << endl << maxNum;
    return 0;
}