Перестройте данный массив, чтобы сделать его отсортированным и GCD элементов, пока i не станет K

Опубликовано: 25 Февраля, 2023

Дано положительное целое число arr[] длины L (2 ≤ L ≤ 2000) содержащий элементы от 1 до L в несортированном порядке и целое число K
(1 ≤ К ≤ 2 * L – 1). Затем задача состоит в том, чтобы вывести расположение arr[] по двум условиям:

  • ∑ НОД i = K для всех (0 ≤ i ≤ L – 1), где НОД i = НОД(A 0, A 1,..., A i ) .
  • arr[] должен быть в отсортированном формате от A 1 до AN – 1 ,

Если такой договоренности не существует , выведите «Невозможно» .

Примеры:

Input: arr[] = {3, 2, 4, 1}, X = 5
Output: 2 1 3 4  

Input: arr[] = {3, 2, 4, 1, 6, 5},  X = 2
Output: Not Possible

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

Arrangement of such arr[] is only possible when (L ≤ K ≤ 2 * L – 1). For output of arrangement see the illustration  of approach.

Иллюстрация подхода:

We have to know the following two things:

  1. In which case of L and R arrangement is possible.
  2. Arrangement of elements.

Let’s discuss them one by one.

  • To Check arrangement is possible or not:-

 Let’s take an random example arr[] = {3, 1, 2}, Then all possible arrangements of arr[] are:

First arrangement: arr[] = {1, 2, 3} 

GCD0 = GCD(1) = 1
GCD1 = GCD(1, 2)= 1
GCD2 = GCD(1, 2, 3) = 1  

Total sum of GCD = 1 + 1 + 1 = 3 

Second arrangement: arr[] = {1, 3, 2}  

Total sum of GCD = 1 + 1 + 1 = 3 

Third arrangement: arr[] = {2, 1, 3}  

Total sum of GCD = 2 + 1 + 1 = 4

 Fourth arrangement: arr[] = {2, 3, 1}  

Total sum of GCD = 2 + 1 + 1 = 4

Fifth arrangement: arr[] = {3, 1, 2}  

Total sum of GCD = 3 + 1 + 1 = 5

Sixth arrangement: arr[] = {3, 2, 1}  

Total sum of GCD = 3 + 1 + 1 = 5 

For all above arrangement we can conclude that the Minimum value and Maximum value of total sum of GCD is equal to 3 and 5 respectively. This gives us idea that arrangement is possible when R lies in the range of [L, L+1.., 2*L-1]. In above arrangements L = 3 and Max and min value of K is 3(equal to L) and 5(equal to 2 * L – 1) respectively.

  • Now Arrangement of elements (excluding cases in which arrangement is not possible):
  1. From above arrangements we can conclude that when K = L, Then, It can be verified that printing counting from 1 to L will give the total sum of GCD equal to K for all valid values of L and R.
  2. For rest of the cases(When L != R), Take first_element as ((K % L) + 1) and print it. Then print rest of the elements from 1 to L excluding first_element(to avoid duplicate, because we have printed it at starting of arrangement). See examples below for clarity:

Example 1: arr[] = {2, 3, 4, 1, 5}, K = 5

L = 5, K = 5, we can clearly see that L is equal to R,  Then print counting from 1 to L:

New arrangement = {1, 2, 3, 4, 5} = GCD0 + GCD1 + GCD2 + GCD3 + GCD4 = 1 + 1 + 1 + 1 + 1 = 5, Total sum of GCD is equal to K, Hence arrangement satisfied as well as in sorted format from index 1 to N – 1.

Example 2: arr[] = {2, 3, 4, 1, 5}, K = 7

L = 5, K = 7, we can clearly see that L is not equal to R, Then first_element = ((K % L) + 1) = ((7 % 5) + 1) = 2 + 1 = 3.

Now print first_element at first index of arrangement and then counting from 1 to L excluding first_element

New arrangement = {3, 1, 2, 4, 5} = GCD0 + GCD1 + GCD2 + GCD3 + GCD4 = 3 + 1 + 1 + 1 + 1 = 7, Total sum of GCD is equal to K, Hence arrangement satisfied as well as in sorted format from index 1 to N – 1.   

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ