Minimum operations to choose Array elements with sum as K by choosing element from front, or rear or both
Given an array arr[] of positive integers of size N, and an integer K. The task is to minimize the number of operations required choose array elements that sum up to K. In one operation, an element can be removed either from the front, or from the rear, or from both front and rear, and added to the sum. If the desired sum can’t be achieved, return -1.
Example:
Input: arr[] = {3, 5, 4, 2, 1}, N = 5, K = 6
Output: 2
Explanation:
- In operation 1, visit index 0 and 4, choose both the elements (3 and 1), thereby making sum as 3 + 1 = 4
- In operation 2, visit index 3 (element 2), thereby making sum as 4 + 2 = 6.
So, minimum operations required = 2
Input: arr[] = {4, 7, 2, 3, 1, 9, 8}, N = 6, K = 9
Output: 3
Approach: Follow the below steps to solve the problem:
- Create a map and take two variables say m1 and m2 for local maxima and global minima respectively.
- Traverse the array and check for the following conditions:
- If the element is greater than or equal to k then continue, because it can’t yield k when added to any other element, as all elements are greater than zero.
- If the element is exactly the half of k, then also continue because here, the task is to find two distinct elements.
- If the position at the map is already filled, that is, if the same element was found earlier then check if that was nearer to any end or this new element is nearer and update the value with that key, else simply check from which end is the element closer and put it in the map.
- If an element is found which was filled earlier in the map and which makes the sum to k with the current element then the time taken will be maximum of picking both the elements and m2 is the minimal of all such distinct pairs that sum to k wherein each pair each number was optimally chosen already, while filling the map.
- After traversing, check for the value of m2. If m2 is still INT_MAX, then return -1, else return m2.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find minimum time required // to visit array elements to get the // sum equal to k int minimumTime( int arr[], int N, int k) { // Create a map map< int , int > mp; // m1 is to keep the local maxima int m1 = 0; // m2 is to keep the global minima int m2 = INT_MAX; // Traverse the array for ( int i = 0; i < N; i++) { // If the element is greater than // or equal to k then continue if (arr[i] >= k) continue ; // If the element is exactly the // half of k, then also continue if (arr[i] == k / 2 && k - arr[i] == k / 2) continue ; // If the position at the map is already filled, // i.e if the same element was found earlier // then check if that was nearer to any end // or this new element is nearer and update // the value with that key, else check from // which end is the element closer and put it // in the map mp[arr[i]] = mp[arr[i]] ? min(mp[arr[i]], min(i + 1, N - i)) : min(i + 1, N - i); // If an element is found which was filled // earlier in the map, which makes the sum // to k with the current element then the // time taken will be maximum of picking // both elements because it is visited // simultaneously if (mp[k - arr[i]]) { m1 = max(mp[arr[i]], mp[k - arr[i]]); // m2 is the minimal of all such distinct // pairs that sum to k where in each pair // each number was optimally chosen already // while filling the map m2 = min(m1, m2); } } // If m2 is still INT_MAX, then there is no such pair // else return the minimum time return m2 != INT_MAX ? m2 : -1; } // Driver Code int main() { int arr[] = { 4, 7, 2, 3, 1, 9, 8 }; int N = sizeof (arr) / sizeof (arr[0]); int K = 6; cout << minimumTime(arr, N, K); return 0; } |
C
#include <stdio.h> #include <stdlib.h> #include <limits.h> #include <limits.h> int min( int a, int b) { return (a < b) ? a : b; } int max( int a, int b) { return (a > b) ? a : b; } // Function to find minimum time required // to visit array elements to get the // sum equal to k int minimumTime( int arr[], int N, int k) { // Create a map int mp[k + 1]; // m1 is to keep the local maxima int m1 = 0; // m2 is to keep the global minima int m2 = INT_MAX; // Traverse the array for ( int i = 0; i < N; i++) { // If the element is greater than // or equal to k then continue if (arr[i] >= k) continue ; // If the element is exactly the // half of k, then also continue if (arr[i] == k / 2 && k - arr[i] == k / 2) continue ; // If the position at the map is already filled, // i.e if the same element was found earlier // then check if that was nearer to any end // or this new element is nearer and update // the value with that key, else check from // which end is the element closer and put it // in the map mp[arr[i]] = mp[arr[i]] ? min(mp[arr[i]], min(i + 1, N - i)) : min(i + 1, N - i); // If an element is found which was filled // earlier in the map, which makes the sum // to k with the current element then the // time taken will be maximum of picking // both elements because it is visited // simultaneously if (mp[k - arr[i]]) { m1 = max(mp[arr[i]], mp[k - arr[i]]); // m2 is the minimal of all such distinct // pairs that sum to k where in each pair // each number was optimally chosen already // while filling the map m2 = min(m1, m2); } } // If m2 is still INT_MAX, then there is no such pair // else return the minimum time return m2 != INT_MAX ? m2 : -1; } int main() { int arr[] = {4, 7, 2, 3, 1, 9, 8}; int N = sizeof (arr) / sizeof (arr[0]); int K = 6; printf ( "%d" , minimumTime(arr, N, K)); return 0; } // This code is contributed by abhinavprkash. |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find minimum time required // to visit array elements to get the // sum equal to k static int minimumTime( int arr[], int N, int k) { // Create a map HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>(); // m1 is to keep the local maxima int m1 = 0 ; // m2 is to keep the global minima int m2 = Integer.MAX_VALUE; // Traverse the array for ( int i = 0 ; i < N; i++) { // If the element is greater than // or equal to k then continue if (arr[i] >= k) continue ; // If the element is exactly the // half of k, then also continue if (arr[i] == k / 2 && k - arr[i] == k / 2 ) continue ; // If the position at the map is already filled, // i.e if the same element was found earlier // then check if that was nearer to any end // or this new element is nearer and update // the value with that key, else check from // which end is the element closer and put it // in the map if (mp.containsKey(arr[i])) mp.put(arr[i], Math.min(mp.get(arr[i]), Math.min(i + 1 , N - i))); else mp.put(arr[i], Math.min(i + 1 , N - i)); // If an element is found which was filled // earlier in the map, which makes the sum // to k with the current element then the // time taken will be maximum of picking // both elements because it is visited // simultaneously if (mp.containsKey(k - arr[i])) { m1 = Math.max(mp.get(arr[i]), mp.get(k-arr[i])); // m2 is the minimal of all such distinct // pairs that sum to k where in each pair // each number was optimally chosen already // while filling the map m2 = Math.min(m1, m2); } } // If m2 is still Integer.MAX_VALUE, then there is no such pair // else return the minimum time return m2 != Integer.MAX_VALUE ? m2 : - 1 ; } // Driver Code public static void main(String[] args) { int arr[] = { 4 , 7 , 2 , 3 , 1 , 9 , 8 }; int N = arr.length; int K = 6 ; System.out.print(minimumTime(arr, N, K)); } } // This code is contributed by 29AjayKumar |
Python3
# Python Program to implement # the above approach # Function to find minimum time required # to visit array elements to get the # sum equal to k def minimumTime(arr, N, k): # Create a map mp = {} # m1 is to keep the local maxima m1 = 0 # m2 is to keep the global minima m2 = 10 * * 9 # Traverse the array for i in range (N): # If the element is greater than # or equal to k then continue if (arr[i] > = k): continue # If the element is exactly the # half of k, then also continue if (arr[i] = = k / / 2 and k - arr[i] = = k / / 2 ): continue # If the position at the map is already filled, # i.e if the same element was found earlier # then check if that was nearer to any end # or this new element is nearer and update # the value with that key, else check from # which end is the element closer and put it # in the map if (arr[i] not in mp): mp[arr[i]] = min (i + 1 , N - i) else : mp[arr[i]] = min ( mp[arr[i]], min (i + 1 , N - i)) # If an element is found which was filled # earlier in the map, which makes the sum # to k with the current element then the # time taken will be maximum of picking # both elements because it is visited # simultaneously if ((k - arr[i]) in mp): m1 = max (mp[arr[i]], mp[k - arr[i]]) # m2 is the minimal of all such distinct # pairs that sum to k where in each pair # each number was optimally chosen already # while filling the map m2 = min (m1, m2) # If m2 is still INT_MAX, then there is no such pair # else return the minimum time return m2 if m2 ! = 10 * * 9 else - 1 # Driver Code arr = [ 4 , 7 , 2 , 3 , 1 , 9 , 8 ] N = len (arr) K = 6 print (minimumTime(arr, N, K)) # This code is contributed by gfgking |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to find minimum time required // to visit array elements to get the // sum equal to k static int minimumTime( int [] arr, int N, int k) { // Create a map Dictionary< int , int > mp = new Dictionary< int , int >(); // m1 is to keep the local maxima int m1 = 0; // m2 is to keep the global minima int m2 = Int32.MaxValue; // Traverse the array for ( int i = 0; i < N; i++) { // If the element is greater than // or equal to k then continue if (arr[i] >= k) continue ; // If the element is exactly the // half of k, then also continue if (arr[i] == k / 2 && k - arr[i] == k / 2) continue ; // If the position at the map is already filled, // i.e if the same element was found earlier // then check if that was nearer to any end // or this new element is nearer and update // the value with that key, else check from // which end is the element closer and put it // in the map if (mp.ContainsKey(arr[i])) mp[arr[i]] = Math.Min( mp[arr[i]], Math.Min(i + 1, N - i)); else mp[arr[i]] = Math.Min(i + 1, N - i); // If an element is found which was filled // earlier in the map, which makes the sum // to k with the current element then the // time taken will be maximum of picking // both elements because it is visited // simultaneously if (mp.ContainsKey(k - arr[i])) { m1 = Math.Max(mp[arr[i]], mp[k - arr[i]]); // m2 is the minimal of all such distinct // pairs that sum to k where in each pair // each number was optimally chosen already // while filling the map m2 = Math.Min(m1, m2); } } // If m2 is still Integer.MAX_VALUE, then there is // no such pair else return the minimum time return m2 != Int32.MaxValue ? m2 : -1; } // Driver Code public static void Main( string [] args) { int [] arr = { 4, 7, 2, 3, 1, 9, 8 }; int N = arr.Length; int K = 6; Console.WriteLine(minimumTime(arr, N, K)); } } // This code is contributed by ukasp |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find minimum time required // to visit array elements to get the // sum equal to k function minimumTime(arr, N, k) { // Create a map let mp = new Map(); // m1 is to keep the local maxima let m1 = 0; // m2 is to keep the global minima let m2 = Number.MAX_VALUE; // Traverse the array for (let i = 0; i < N; i++) { // If the element is greater than // or equal to k then continue if (arr[i] >= k) continue ; // If the element is exactly the // half of k, then also continue if (arr[i] == Math.floor(k / 2) && k - arr[i] == Math.floor(k / 2)) continue ; // If the position at the map is already filled, // i.e if the same element was found earlier // then check if that was nearer to any end // or this new element is nearer and update // the value with that key, else check from // which end is the element closer and put it // in the map if (!mp.has(arr[i])) { mp.set(arr[i], Math.min(i + 1, N - i)) } else { mp.set(arr[i], Math.min(mp.get(arr[i]), Math.min(i + 1, N - i))) } // If an element is found which was filled // earlier in the map, which makes the sum // to k with the current element then the // time taken will be maximum of picking // both elements because it is visited // simultaneously if (mp.has(k - arr[i])) { m1 = Math.max(mp.get(arr[i]), mp.get(k - arr[i])); // m2 is the minimal of all such distinct // pairs that sum to k where in each pair // each number was optimally chosen already // while filling the map m2 = Math.min(m1, m2); } } // If m2 is still INT_MAX, then there is no such pair // else return the minimum time return m2 != Number.MAX_VALUE ? m2 : -1; } // Driver Code let arr = [4, 7, 2, 3, 1, 9, 8]; let N = arr.length; let K = 6; document.write(minimumTime(arr, N, K)); // This code is contributed by Potta Lokesh </script> |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(N)