Given a sorted array arr[] of positive integers of size K, and an integer N, where some numbers can be inserted into the array such that all positive integers [1, N] can be obtained as a sum of subsets of the modified array. The task is to find the minimum number of insertions required.
Note: Minimum length of the array can be 1.
Examples:
Input: K = 2, arr = [1, 2], N = 4
Output: 1
Explanation We need to insert either 3 or 4 in the array.Input: K = 4, arr = [1, 2, 4, 8], N = 15
Output: 0
Approach: This problem can be solved using Greedy Approach.
- Form a list say X[] of essential elements needed to form a sum up to N by including some elements from the given array arr[] and/or adding other missing elements that are required.
- Initially, begin with the empty list X[], the range of possible sums using numbers from X[] is [0, 0].
- Suppose that the elements in the range [1, m] (m < N) can be represented as a sum of the elements present in the list X[] at that instant, and numbers till index i of the arr[] have been added.
Below are the following possibilities:
- If the (i+1)th number of arr[] is = (m + 1), then the extra sums possible are:
(m + 1), (m + 2), (m + 3)…, (m + m + 1).
Hence, the range becomes [1, ((2 * m) + 1)]. Add the number arr[i+1] to X[]. Increment the value of i.- If the (i+1)th number of arr[] is < (m + 1), let it be k, then extra sums possible are:
(1 + k), (2 + k), (3 + k), …(m + k).
Hence, the range becomes [1, (m + k)]. Add the number arr[i+1] to X[] Increment the value of i.- If the (i+1)th number of arr[] is > (m + 1), then (m + 1) should be inserted to the array X[], else there is no way to obtain a sum of (m + 1) by these numbers.
Hence, the range becomes [1, ((2 * m) + 1)] after insertion of (m + 1). Do not increment the value of i.
- Repeat this process until the range crosses the given number N.
- Even after doing so, if all the numbers in the array arr[] are traversed, and the range hasn’t crossed N, then there is a need to keep on adding more and more numbers to X[] till the range crosses N.
- The difference between the sizes of X[] and arr[] is the required minimum number of insertions to be made.
- After including all the essential elements in X[] the range should be at least [1, N] with a minimum number of insertions from outside the given list.
Note: Instead of maintaining a list X[], a counter variable ans can be initialised to 0 and everytime a new element is added the counter value can be incremented. The value of the counter variable is the required answer.
Below is the implementation of the above approach:
C++
// C++ code to minimize insertions// such that sum of subsets of// array elements form all numbers// up to N#include <bits/stdc++.h>using namespace std;#define N 100005int minInsertions(vector<int>& v, int n){ // initialised rangeEnd which // denotes the range covered, // [1, rangeEnd] ans denotes // the number of insertions made // so far int rangeEnd = 0, ans = 0; for (auto i : v) { // in the case where our next // number is greater than // rangeEnd+1, it is compulsory // to insert rangeEnd+1 while (i > rangeEnd + 1) { ans++; rangeEnd = rangeEnd * 2 + 1; if (rangeEnd >= n) { return ans; } } // otherwise we just move // forward our rangeEnd rangeEnd += i; if (rangeEnd >= n) { return ans; } } // after we have included all // elements in the array and have // still not reached n, we insert // numbers = rangeEnd+1 till // we reach n while (rangeEnd < n) { ans++; rangeEnd = rangeEnd * 2 + 1; } return ans;}// Driver Programsigned main(){ // the size of the given array int k = 4; // the given number n int n = 15; std::vector<int> v = { 1, 6, 7, 9 }; cout << minInsertions(v, n); return 0;} |
Java
// Java code to minimize insertions // such that sum of subsets of // array elements form all numbers // up to N class GFG{ int N = 100005; static int minInsertions(int []v, int n) { // initialised rangeEnd which // denotes the range covered, // [1, rangeEnd] ans denotes // the number of insertions made // so far int rangeEnd = 0, ans = 0; for (int i : v) { // in the case where our next // number is greater than // rangeEnd+1, it is compulsory // to insert rangeEnd+1 while (i > rangeEnd + 1) { ans++; rangeEnd = rangeEnd * 2 + 1; if (rangeEnd >= n) { return ans; } } // otherwise we just move // forward our rangeEnd rangeEnd += i; if (rangeEnd >= n) { return ans; } } // after we have included all // elements in the array and have // still not reached n, we insert // numbers = rangeEnd+1 till // we reach n while (rangeEnd < n) { ans++; rangeEnd = rangeEnd * 2 + 1; } return ans; } // Driver Program public static void main (String[] args) { // the size of the given array int k = 4; // the given number n int n = 15; int v[] = { 1, 6, 7, 9 }; System.out.println(minInsertions(v, n)); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 program to minimize insertions# such that sum of subsets of# array elements form all numbers# up to NN = 100005 def minInsertions(v, n): # Initialised rangeEnd which # denotes the range covered, # [1, rangeEnd] ans denotes # the number of insertions made # so far rangeEnd, ans = 0, 0 for i in v: # In the case where our next # number is greater than # rangeEnd+1, it is compulsory # to insert rangeEnd+1 while (i > rangeEnd + 1): ans += 1 rangeEnd = rangeEnd * 2 + 1 if (rangeEnd >= n): return ans # Otherwise we just move # forward our rangeEnd rangeEnd += i if (rangeEnd >= n): return ans # After we have included all # elements in the array and have # still not reached n, we insert # numbers = rangeEnd+1 till # we reach n while (rangeEnd < n): ans += 1 rangeEnd = rangeEnd * 2 + 1 return ans # Driver codeif __name__ == "__main__": # The size of the given array k = 4 # The given number n n = 15 v = [ 1, 6, 7, 9 ] print(minInsertions(v, n))# This code is contributed by chitranayal |
C#
// C# program to minimize insertions // such that sum of subsets of // array elements form all numbers // up to N using System;class GFG{//int N = 100005; static int minInsertions(int []v, int n) { // Initialised rangeEnd which // denotes the range covered, // [1, rangeEnd] ans denotes // the number of insertions made // so far int rangeEnd = 0, ans = 0; foreach(int i in v) { // In the case where our next // number is greater than // rangeEnd+1, it is compulsory // to insert rangeEnd+1 while (i > rangeEnd + 1) { ans++; rangeEnd = rangeEnd * 2 + 1; if (rangeEnd >= n) { return ans; } } // Otherwise we just move // forward our rangeEnd rangeEnd += i; if (rangeEnd >= n) { return ans; } } // After we have included all // elements in the array and have // still not reached n, we insert // numbers = rangeEnd+1 till // we reach n while (rangeEnd < n) { ans++; rangeEnd = rangeEnd * 2 + 1; } return ans; } // Driver code public static void Main(String[] args){ // The size of the given array //int k = 4; // The given number n int n = 15; int []v = { 1, 6, 7, 9 }; Console.WriteLine(minInsertions(v, n)); } }// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript code to minimize insertions // such that sum of subsets of // array elements form all numbers // up to N let N = 100005; function minInsertions(v, n) { // initialised rangeEnd which // denotes the range covered, // [1, rangeEnd] ans denotes // the number of insertions made // so far let rangeEnd = 0, ans = 0; for (let i in v) { // in the case where our next // number is greater than // rangeEnd+1, it is compulsory // to insert rangeEnd+1 while (i > rangeEnd + 1) { ans++; rangeEnd = rangeEnd * 2 + 1; if (rangeEnd >= n) { return ans; } } // otherwise we just move // forward our rangeEnd rangeEnd += i; if (rangeEnd >= n) { return ans; } } // after we have included all // elements in the array and have // still not reached n, we insert // numbers = rangeEnd+1 till // we reach n while (rangeEnd < n) { ans++; rangeEnd = rangeEnd * 2 + 1; } return ans; } // Driver Code // the size of the given array let k = 4; // the given number n let n = 15; let v = [ 1, 6, 7, 9 ]; document.write(minInsertions(v, n)); </script> |
Output:
2
Time Complexity: O(K + log(N))
Auxiliary Space: O(1) because it is using constant space for variables
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
