Minimum possible value of D which when added to or subtracted from K repeatedly obtains every array element

Minimum possible value of D which when added to or subtracted from K repeatedly obtains every array element

Given an array arr[] of size N and an integer K, the task is to find the maximum possible value of D, such that every array element can be obtained, starting from the initial value of K, by either changing K to K – D or K + D at each step.

Examples:

Input: arr[ ] = {1, 7, 11}, K = 3
Output: 2
Explanation:
Considering the value of D to be 2, every array element can be obtained by the following operations:

• arr[0](= 1):  Decrementing 2 from K(=3) obtains arr[0].
• arr[1](= 7): Incrementing K(=3) by 2 times D obtains arr[1].
• arr[2](= 11): Incrementing K(=3) by 4 times D obtains arr[2].

Therefore, D (=2) satisfies the conditions. Also, it is the maximum possible value of D.

Input: arr[ ] = {33, 105, 57}, K = 81
Output: 24

Approach: The problem can be solved by finding the Greatest Common Divisor of the absolute difference between each array element and K. Follow the steps below to solve the problem

• Traverse the array arr[], and change the value of the current element arr[i] to abs(arr[i] – K).
• Initialize a variable, say D as arr[0], to store the result.
• Iterate in the range [1, N – 1] using a variable, say i, and in each iteration, update the value of D to gcd(D, arr[i]).
• After completing the above steps, print the value of D as the answer.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std;    int gcd(int a, int b) {     if (b == 0)         return a;        return gcd(b, a % b); }    int findMaxD(int arr[], int N, int K) {          for (int i = 0; i < N; i++) {                     arr[i] = abs(arr[i] - K);     }             int D = arr[0];             for (int i = 1; i < N; i++) {                     D = gcd(D, arr[i]);     }             return D; }    int main() {        int arr[] = { 1, 7, 11 };     int N = sizeof(arr) / sizeof(arr[0]);     int K = 3;        cout << findMaxD(arr, N, K);     return 0; }

Time Complexity: O(N*log(N))
Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the Essential Maths for CP Course at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets