Minimize insertions to make sum of every pair of consecutive array elements at most K

Minimize insertions to make sum of every pair of consecutive array elements at most K

Given an array arr[] of N positive integers and an integer K, the task is to find the minimum number of insertions of any positive integers is required such that the sum of every adjacent element is at most K. If it is not possible, then print “-1”.

Examples:

Input: arr[] = {1, 2, 3, 4, 5}, K = 6
Output: 2
Explanation:
Following insertions are required:
Operation 1: Insert 1 between indices 2 and 3. Therefore, the array modifies to {1, 2, 3, 1, 4, 5}.
Operation 2: Insert 1 between index 4 and 5. Therefore, the array modifies to {1, 2, 3, 1, 4, 1, 5}. Therefore, the minimum number of insertions required is 2.

Input: arr[] = {4, 5, 6, 7, 7, 8}, K = 8
Output: -1

Approach: The idea is based on the fact that inserting 1 between the elements whose sum exceeds K makes the sum of consecutive elements less than K if the element itself is not equal to or greater than K. Follow the steps below to solve the given problem:

• Initialize three variables, say res = 0, possible = 1, and last = 0 to store the count of minimum insertions, to check if it is possible to make the sum of all consecutive pairs at most K or not, and to store the previous number to the current element respectively.
• Traverse the array arr[] and perform the following steps:
  • If the value of arr[i] is at least K, then it is not possible to make the sum of all consecutive pairs at most K.
  • If the sum of last and arr[i] is greater than K, then increment res by 1 and assign last = arr[i].
• After completing the above steps, if the value of possible is 1, then print the value of res as the minimum number of insertions required. Otherwise, print “-1”.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std;    void minimumInsertions(int arr[],                        int N, int K) {                    bool possible = 1;             int res = 0;                  int last = 0;             for (int i = 0; i < N; i++) {                              if (arr[i] >= K) {                             possible = 0;             break;         }                              if (last + arr[i] > K)                             res++;                     last = arr[i];     }                  if (possible) {         cout << res;     }             else {            cout << "-1";     } }    int main() {     int arr[] = { 1, 2, 3, 4, 5 };     int K = 6;     int N = sizeof(arr) / sizeof(arr[0]);        minimumInsertions(arr, N, K);        return 0; }

Time Complexity: O(N)
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.

Let's block ads! (Why?)