Минимальные приращения, необходимые для того, чтобы сделать пару X с элементами массива не взаимно простыми

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

Дано целое число arr[] длины N такое, что (A i > 0) для всех (1 ≤ i ≤ N) и целое число X. За одну операцию вы можете добавить 1 либо к X, либо к arr[i] , чтобы сделать НОД (X, A i ) не равно 1. Помните, что приращение значений X или arr[i] будет постоянным. Формально, если какое-либо значение увеличивается в какой-либо операции, исходное значение также изменится.

Затем ваша задача состоит в том, чтобы напечатать все нижеперечисленные вещи на выходе:

  • Минимальное количество операций, необходимых для получения НОД(X i , arr[i]) не равно 1 для всех (1 ≤ i ≤ N) .
  • обновленный обр[]
  • значения X для каждого действительного i .

Примеры:

Input 1: N = 5, arr[] = {4,3,1,4,6}, X = 3
Output 1: 3
arr[] = {4, 4, 2, 4, 6}
X[] = {4, 4, 4, 4, 4}
Explanation: There are minimum 3 operations required so that GCD(Xi, arr[i]) ≠ 1. Three operations are defined below:

  • At index 1: Initially arr[1] = 4 and X = 3. GCD(3, 4) = 1.Therefore, X increment to 3+1=4. So that GCD(4, 4) =4, Which is not equal to 1 now. X altered from 3 to 4 permanently for next values of index i.  
  • At index 2: arr[2] = 3  and X = 4. GCD(3, 4) = 1.Therefore, arr[2] increment to 3+1 = 4. So that GCD(4, 4) = 4, Which is not equal to 1. arr[2] altered from 3 to 4 permanently. 
  • At index 3: arr[3] altered to 1+1 = 2 and X = 4. So that GCD(X, arr[3]) at index 3 is : GCD(4, 2) = 2, Which is not equal to 1.

It can be verified that there is no such pair of Xi and arr[i] exist for (1<=i<=N) in output such that GCD(Xi, arr[i]) =1. So, Minimum operations required are 3.

Input 2: N = 3, arr[] = {4, 8, 2}, X = 2
Output 2: 0
arr[] = {4, 8, 2}
X[] = {2, 2, 2}
Explanation: All the pair of X and arr[i] for each valid i has GCD not equal to 1.Therefore, 0 operations required. 

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

GCD of any two integers let say X and Y can be made greater than 1 easily under 0, 1 or 2 operations. By following this hint we can alter the values of X or arr[i] to make GCD greater than 1. For clear explanation see the concept of approach below.      

Концепция подхода:

For this problem we just need to find to minimum operation required to make GCD of two number greater than 1 at each valid position of i, Then altering the value of X or arr[i] is not a big deal. The problem can be divided in sub-parts as :

      1. if X and arr[i] both are even at any index i or the GCD(X, arr[i]) is already greater than 1, Then:

  • X and arr[i] will remain same.
  • Minimum Operations required = 0.   

      2. if value of either GCD(arr[i]+1, X) or GCD(arr[i], X+1) is not equal to 1, Then:

  • Increment the element X or arr[i], Which gives GCD greater than 1.
  • Minimum Operations required = 1.   

      3. If none of the above condition met, Then:

  • Increment both X and arr[i].
  • Minimum Operations required= 2 .  

It can be verified that the value of GCD(Xi , arr[i]) can make greater than 1 by one of the above operation all the possible pairs of X and arr[i]. 

Иллюстрация подхода (с использованием обсуждавшихся выше 3 частей проблемы):

Input: N = 4, arr[] = {1, 4, 3, 5}, X = 1
Output: Minimum operations required : 4
arr[]: [2, 4, 4, 6]
Values of X:  [2, 2, 2, 2]

Explanation:

At index 1: arr[1] = 1, X =1, GCD(1, 1) = 1

  • GCD can be altered from 1 using sub-part 3 of the problem, Which is incrementing both X and arr[i]. Then,
  • GCD = (X+1, arr[1]+1) = GCD(2, 2) = 2 ≠ 1. X and arr[1] altered to 2 and 2 respectively. Minimum operations required = 2. Total operations till now = 2.

At index 2: arr[2] = 4, X = 2, GCD(4, 2) = 2, 

  • Already not equal to 1 and related to sub-part 1 of the problem, Which is not to alter any of X or arr[i]. Minimum operations required = 0.  Total operations till now = 2.

At index 3: arr[3] = 3, X = 2, GCD(3, 2) = 1

  • GCD can be altered using sub-part 2 of the problem, Which is incrementing arr[i]. Then,
  • GCD = (X, arr[1]+1) = GCD(4, 2) = 2 ≠ 1. X and arr[3] altered to 2 and 4 respectively. Minimum operations required = 1. Till now total operations = 3.

At index 4: arr[4] = 5, X = 2, GCD(5, 2) = 1

  • GCD can be altered using sub-part 2 of the problem, Which is incrementing arr[i]. Then,
  • GCD = (X, arr[1]+1) = GCD(2, 5+1) = 2 ≠ 1. X and arr[4] altered to 2 and 6 respectively. Minimum operations required = 1. Total operations till now = 4.

So, Total number of operations required are 4. Altered values of X or arr[i] will permanent.  

arr[] = {arr[1], arr[2], arr[3], arr[4]} = {2, 4, 4, 6} (updated arr[] with altered values)

X[] = {2, 2, 2, 2}

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

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

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