Answers for "kth smallest element solution"

kth smallest number again

void solve() {

	int n, q;
	cin >> n >> q;
	// v =  [{1, 7}, {10, 15}]
	vector<pair<int, int>> arr(n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i].ff >> arr[i].ss;
	}

	// v =  [{10, 15}, {1, 7}]

	sort(arr.begin(), arr.end());

	// v = [{1, 7}, {10, 15}];

	// case : v = [{1, 7}, {15, 10}];
	int idx = 0;
	for (int i = 1; i < n; i++) {
		if (arr[idx].ff > arr[idx].ss) {
			arr[idx].ss = max(arr[idx].ff, arr[idx].ss);
		}
		else {
			idx++;
			arr[idx] = arr[i];
		}
	}

	// Searching
	while (q--) {

		int k;
		cin >> k;

		int ans = -1;
		for (int i = 0; i <= idx; i++) {
			if (arr[i].ss - arr[i].ff + 1 > k) {
				ans = arr[i].ff + k - 1;
				break;
			}
			else {
				k -= arr[i].ss - arr[i].ff + 1;
			}
		}
		cout << ans << 'n';
	}



}

Kth Smallest element

import random

def swap(A, i, j):
    A[i], A[j] = A[j], A[i]

def partition(A, lo, hi):
    pivot = A[lo]
    i = lo + 1
    j = hi

    while True:
        while A[i] < pivot:
            i += 1
            if i == hi:
                break
        while A[j] > pivot:
            j -= 1
            if j == lo:
                break
        if j <= i:
            break
        swap(A, i, j)
    swap(A, lo, j)
    print(A)
    return j

def k_smallest(A, k):
    lo = 0
    hi = len(A) - 1
    k = k - 1
    random.shuffle(A)

    while hi > lo:
        j = partition(A, lo, hi)
        if j == k:
            return A[k]
        elif j > k:
            hi = j - 1
        else:
            lo = j + 1

    return A[k]