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.