Minimum Operations to Choose Array Elements with Sum as K by Choosing an Element from the Front, or Rear or Both

Introduction

Hash Maps are one of the most important data structures having a wide range of applications. These are one of the more advanced data structures but are still rather easy to implement. These are also about in the technical interviews of numerous big tech companies. They can also be used to solve numerous problems ranging across various difficulty levels.

Check out Hashing

Problem Statement

The problem is to find Minimum operations to choose Array elements with sum as K by choosing an element from the front, or rear or both.

We are given N numbers in an array and a sum K. We can take elements either from the front, rear, or both positions to get the sum as K.

Sample Example

Example: Say we have 5 elements in an array given as 3, 5, 4, 2, 1.

And the sum given is 6.

We have to find the minimum number of operations to obtain our given sum.

Here on removing 3 and 1 both in the first operation, our sum becomes 4, then removing 2 in the second operation, our sum becomes 6.

See Implementation of Hashmap

Approach

The approach to finding Minimum operations to choose Array elements with sum as k by choosing an element from the front, or rear, or both can be proceeded by using maps.

Declare a map and two variables, one for local maxima and the other for global minima.

⬇

Start traversing the array.

⬇

If the element extracted is greater than or equal to k, then continue. Also if the element is exactly half of k, then also continue.

⬇

If the position at the map is filled or occupied, i.e. if the same element was found before, then check if that was nearer to any end(front or rear) or this new element is nearer and then update the value with that key, else go for checking from which end is the element closer and put it in the map.

⬇

Suppose an element is found which was filled earlier in the map, which makes the sum to k with the current element. In that case, the time taken will be the maximum of picking both elements because it is visited simultaneously.

⬇

 m2 is the minimal(minimum) of all such distinct pairs that sum or aggregate to k wherein each pair and each number was optimally chosen while filling the map.

⬇

If m2 is still INT_MAX, then there must be no such pair, return the minimum time.

Till now, I assume you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try.

try here

Please have a look at the algorithm, and then again, you must give it a try.

PseudoCode

Algorithm 

___________________________________________________________________

procedure minimumTime(int arr[], int N, int k):

___________________________________________________________________

1.  map<int, int> mp

2.  m1 = 0, m2 = INT_MAX

3.  Begin loop. Traverse till N.

4.  if (arr[i] >= k): continue;

5.  if (arr[i] == k / 2 && k - arr[i] == k / 2): continue;

6.   mp[arr[i]] = mp[arr[i]] ? min(mp[arr[i]], min(i + 1, N - i)) : min(i + 1, N - i);

7.  if (mp[k - arr[i]]):

m1 = max(mp[arr[i]], mp[k - arr[i]]);

m2 = min(m1, m2)

8.  return m2 != INT_MAX ? m2 : -1;

end procedure

___________________________________________________________________

Implementation in C++

// C++ program to calculate minimum operations to choose Array elements with sum as K by choosing element from front, or rear or both
#include <bits/stdc++.h>
using namespace std;

// Function to find minimum time to traverse the array to get their sum=K.
int minimumTime(int arr[], int N, int k)
{
	// Creating a map
	map<int, int> mp;

	// m1 - the local maxima
	int m1 = 0;

	// m2 - the global minima here
	int m2 = INT_MAX;

	// Traversing the entire array
	for (int i = 0; i < N; i++)
	{

		// If the element extracted is greater than or equal to k then continue
		if (arr[i] >= k)
			continue;

		// If the element is exactly thehalf of k, then continue
		if (arr[i] == k / 2 && k - arr[i] == k / 2)
			continue;

		// If the position or the particular place at the map is already filled,i.e if the same element was found before then check if that was closer to any end or this new element is closer and update the value with that key, else check from which end is the element nearer and put it in our 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 encountered which was filled before in the map, which makes our sum equals k with the current element then the time taken will be maximum of picking both elements because it is visited simultaneously(at the same time).
		if (mp[k - arr[i]])
		{
			m1 = max(mp[arr[i]], mp[k - arr[i]]);

			// m2 is the minima(minimum) of all such distinct pairs that sum to k wherein each pair each number was chosen optimally already while filling our map container.
			m2 = min(m1, m2);
		}
	}
	// If m2 is still being INT_MAX, then there is no such pair else return the minimum time
	return m2 != INT_MAX ? m2 : -1;
}

int main()
{
	int n, k;
	cin >> n;
	int arr[n];
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	cin >> k;

	cout << minimumTime(arr, n, k);

	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Sample Input: 
5
3 5 4 2 1
6
Sample Output:
2

Complexity Analysis

Time Complexity: O(n).

Analyzing Time Complexity:

In the worst case, all elements are traversed once. O(n)

Space complexity: O(n).

You can also read about the Longest Consecutive Sequence.