Largest quantity to create given Array by including or subtracting Okay a number of occasions

Given an integer Okay and an array arr[] of N integers, the duty is to search out the utmost quantity that may be added or subtracted any variety of occasions from Okay to get all of the array components.

Examples:

Enter: Okay = 5, N = 3, arr = {3, 7, 13}
Output: 2
Rationalization: As at present Okay is 5 we are able to subtract 2 to get 3 now Okay turn out to be 3.
After this we are going to add two occasions 2 in 3 to type 7. Now Okay is 7.
After this we are going to add 2 thrice to type 13.

Enter: Okay = 6, N = 3, arr = {11, 6, 2}
Output: 1

Strategy: The issue may be solved based mostly on the next statement:

To get the utmost worth, we should choose the best worth which is an element of the variations of Okay with all of the array components, i.e., the GCD of the variations of all of the array components with Okay.

Observe the beneath steps to unravel this drawback:

• Retailer the distinction of all of the array components from Okay in an array (say temp[]).
• Iterate over the array arr[]:
  • Retailer absolutely the distinction between Okay and the present array component in temp[].
• Initialize a variable (say ans = 0) to retailer the reply.
• Iterate over temp[]:
  • Replace reply with the GCD of ans and the present component’s worth of temp[].
• Return the worth of ans because the required reply.

Beneath is the implementation of the above strategy.

Time Complexity: O(N * logD) the place D is the utmost distinction of an array component with Okay
Auxiliary House: O(N)