Find K-th Minimum Element from Array Concatenated m Times in C++

Consider we have an array A, and another two integers K and M. We have to find Kth minimum element after concatenating the array to itself M number of times. Suppose the array is like A = [3, 1, 2], K = 4 and M = 3, so after concatenating A, 3 times, it will be [3, 1, 2, 3, 1, 2, 3, 1, 2], the 4th smallest element is 2 here.

To solve this problem, we will sort the array A, then return the value, present at index ((K – 1)/M), of the array.

Example

 Live Demo

#include<iostream>
#include<algorithm>
using namespace std;
int findKSmallestNumber(int A[], int N, int M, int K) {
   sort(A, A + N);
   return (A[((K - 1) / M)]);
}
int main() {
   int A[] = { 3, 1, 2 };
   int M = 3, K = 4;
   int N = sizeof(A) / sizeof(A[0]);
   cout << K << "th smallest number after concatenating " << M << " times, is: "<<findKSmallestNumber(A, N, M, K);
}

Output

4th smallest number after concatenating 3 times, is: 2