Sắp xếp phần tử nằm giữa các bội số của K trong mảng trong C++

Cho mảng A và số nguyên K. Sắp xếp các phần tử nằm giữa hai bội số liên tiếp của K. Ví dụ A = [2, 13, 3, 1, 21, 7, 8, 13, 12], K = 2. Các bội của 2: 2, 8, 12. Phần tử giữa 2 và 8: [13,3,1,21,7] → sắp thành [1,3,7,13,21]. Giữa 8 và 12 chỉ có 13 → giữ nguyên. Kết quả: [2, 1, 3, 7, 13, 21, 8, 13, 12].

Duyệt mảng, ghi nhớ chỉ số bội số trước đó. Khi gặp bội số mới (từ bội thứ 2), sort đoạn giữa bội trước và bội hiện tại.

Ví dụ

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

void display(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

void sortBetweenMultipleOfK(int arr[], int n, int k) {
    int prev_index = -1;
    for (int i = 0; i < n; i++) {
        if (arr[i] % k == 0) {
            if (prev_index != -1)
                sort(arr + prev_index + 1, arr + i);
            prev_index = i;
        }
    }
}

int main() {
    int arr[] = {2, 13, 3, 1, 21, 7, 8, 13, 12};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << "Before Sort: "; display(arr, n);
    sortBetweenMultipleOfK(arr, n, k);
    cout << "\nAfter Sort : "; display(arr, n);
}

Kết quả

Before Sort: 2 13 3 1 21 7 8 13 12 After Sort : 2 1 3 7 13 21 8 13 12