Reduce the array to a single element with the given operation

Given an integer K and an array of integers, you have to find whether is it possible to reduce the array to a single element equal to k or not.

You can do the following operation:
1) Pick any two elements a[i] and a[j] in the array such that i!=j
2) Remove both the elements a[i] and a[j] and instead add a number x such that x lies between [min(a[i], a[j]) and max(a[i], a[j])] both inclusive.

After applying the above operations N – 1 times, you will end up with a single number in the array.
Find whether it is possible to do the operations in such a way that you end up with a number K.

Examples:

Input: K = 6, arr = {3 6 9 12} 
Output: Yes arr = {3 6 9 12} 
// now replace 3, 6 with 3 arr = {3 9 12} 
// now replace 3, 9 with 3 arr = {3 12} 
// now replace 3, 12 with 6 arr = {6} = K 

Input: K = 20 , arr = {3 6 9 12} 
Output: No

Approach:
We can notice that at every step since we are replacing a[i] and a[j] with x such that x lies between [min(a[i], a[j]) and max(a[i], a[j])] both inclusive.
So we will always end with a number which will always lie in range [min of the array,max of the array] both inclusive.
For eg arr = {3 6 9 12}
// now replace 3, 6 with 3 arr = {3 9 12}
// now replace 3, 9 with 3 arr = {3 12}
// now replace 3, 12 with 6 arr = {last element can be now any no in range min to max of the array inclusive} 3 = min of the array, 12 = max of the array.

So we just have to check that if k lies in the range [min(Arr),max(Arr)] both inclusive.

Below is the implementation of the above approach:

#include<bits/stdc++.h>
using namespace std;

// Function to check if it is possible to end with k
void isPossible(int A[], int n, int k)
{
    int mn = INT_MAX;
    int mx = INT_MIN;
    for(int i = 0; i < n; i++)
    {
        mn = min(mn, A[i]);
        mx = max(mx, A[i]);
    }

    cout << ((k >= mn) && (k <= mx) ? "Yes" : "No");
}

// Driver program to test the case
int main()
{
    int arr[] = {1, 2, 4, 5};
    int k = 5;
    int n = sizeof(arr)/sizeof(arr[0]);
    isPossible(arr, n, k);
    return 0;
}

Output:

Yes

Time Complexity: O(n)
Time Complexity: O(1)

Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.