Thursday, September 28, 2023
HomeSoftware DevelopmentDiscover Ok such that repeated subtraction of Ok from Array components make...

# Discover Ok such that repeated subtraction of Ok from Array components make the Array equal

Given an array arr[] of size N, the task is to find the value of an integer K such that its repeated subtraction from array elements will make all array elements in minimum operations.

Example:

Input: arr[] = {5, 3, 3, 7}
Output: 2
Explanation: Minimum 2 operations must be performed:
1st operation: subtract 2 from elements at indices {0, 3}, arr[] = {3, 3, 3, 5}
2nd operation: subtract 2 from element at index 3, arr[] = {3, 3, 3, 3}
So, the value of K = 2

Input: arr[] = {-1, 0, -1, 0, -1}
Output: 1

Approach: To make all elements in the array arr equal, all elements need to be changed to the smallest value in the array. So, the gcd of the difference of all array elements to the smallest element will be the value of K. Now, to solve the following problem, follow the below steps:

1. Create a variable mn to store the minimum element in the array arr.
2. Now, traverse the array arr and find the gcd of the differences between all array elements and mn. Store this value in a variable K.
3. Return K, as the answer to this question.

Below is the implementation of the above approach:

## C++

 `#include ``using` `namespace` `std;` `int` `findtheValue(``int` `arr[], ``int` `N)``{``    ``    ``int` `mn = *min_element(arr, arr + N);` `    ``int` `K = arr[0] - mn;` `    ``    ``    ``    ``for` `(``int` `i = 1; i < N; ++i) {``        ``K = __gcd(K, arr[i] - mn);``    ``}` `    ``return` `K;``}` `int` `main()``{``    ``int` `arr[] = { 5, 3, 3, 7 };``    ``int` `N = ``sizeof``(arr) / ``sizeof``(arr[0]);``    ``cout << findtheValue(arr, N);` `    ``return` `0;``}`

## Python3

 `import` `math` `def` `findtheValue(arr, N):` `    ``    ``mn ``=` `min``(arr)` `    ``K ``=` `arr[``0``] ``-` `mn` `    ``    ``    ``    ``for` `i ``in` `range``(``1``, N):``        ``K ``=` `math.gcd(K, arr[i] ``-` `mn)` `    ``return` `K` `if` `__name__ ``=``=` `"__main__"``:` `    ``arr ``=` `[``5``, ``3``, ``3``, ``7``]``    ``N ``=` `len``(arr)``    ``print``(findtheValue(arr, N))`

Time Complexity: O(Nlog(mn))
Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.

RELATED ARTICLES