Given an integer K and an array arr[] of N integers, the task is to find the maximum number that can be added or subtracted any number of times from K to get all the array elements.
Examples:
Input: K = 5, N = 3, arr = {3, 7, 13}
Output: 2
Explanation: As currently K is 5 we can subtract 2 to get 3 now K become 3.
After this we will add two times 2 in 3 to form 7. Now K is 7.
After this we will add 2 three times to form 13.Input: K = 6, N = 3, arr = {11, 6, 2}
Output: 1
Approach: The problem can be solved based on the following observation:
To get the maximum value, we must select the highest value which is a factor of the differences of K with all the array elements, i.e., the GCD of the differences of all the array elements with K.
Follow the below steps to solve this problem:
- Store the difference of all the array elements from K in an array (say temp[]).
- Iterate over the array arr[]:
- Store the absolute difference between K and the current array element in temp[].
- Initialize a variable (say ans = 0) to store the answer.
- Iterate over temp[]:
- Update answer with the GCD of ans and the current element’s value of temp[].
- Return the value of ans as the required answer.
Below is the implementation of the above approach.
C++
|
|
Time Complexity: O(N * logD) where D is the maximum difference of an array element with K
Auxiliary Space: O(N)