Создайте массив размером N, чтобы каждый подмассив размера K имел значение MEX D

Даны три целых числа N , K и D , задача состоит в том, чтобы построить массив размера N так, чтобы каждый подмассив размера K имел значение MEX, равное D . Если нет возможного ответа, выведите -1.

MEX of an array is the first non-negative integer that is not present in the array.

Примеры:

Input:  N = 4, K = 3, D = 4
Output: -1
Explanation:  As D exceeds K, it is impossible to generate desired array.

Input:  N = 4, K = 3, D = 3
Output:  0 1 2 0
Explanation:  All subarray of size 3 i.e., {0, 1, 2}, {1, 2, 0} has mex value 3.

Input:  N = 4, K = 3, D = 2
Output: 0 1 0 1
Explanation: All subarray of size 3 i.e., {0, 1, 0}, {1, 0, 1} has mex value 2.

Подход: нам нужно следовать конструктивному подходу, чтобы решить вышеуказанную проблему.

Check whether D exceeds K, If so then print -1.

Else we can construct the solution:

• Take first K elements of desired array including from 0 to D-1, then including elements after D onwards.
• For remaining next K positions we need to print above elements in cyclic order.
• Repeat the above process until desired length is not achieved.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)