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

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

Examples:

Enter: Okay = 5, N = 3, arr = {3, 7, 13}
Output: 2
Clarification: As at present Okay is 5 we are able to subtract 2 to get 3 now Okay develop into 3.
After this we’ll add two instances 2 in 3 to type 7. Now Okay is 7.
After this we’ll add 2 3 times to type 13.

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

Method: The issue will be solved based mostly on the next statement:

To get the utmost worth, we should choose the very 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 resolve this downside:

• 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.

Under is the implementation of the above method.

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