Minimum number of insertions required such that first K natural numbers can be obtained as sum of a subsequence of the array

0 0 7 minutes read

Given an array arr[] consisting of N positive integers and a positive integer K, the task is to find the minimum number of elements that are required to be inserted such that all numbers from the range [1, K] can be obtained as the sum of any subsequence of the array.

Examples:

Input: arr[] = {1, 3, 5}, K = 10
Output: 1
Explanation:
Appending the element {1} to the array modifies the array to {1, 3, 5, 1}. Now the all the sum over the range [1, K] can be obtained as:

Sum 1: The elements are {1}.

Sum 2: The elements are {1, 1}.

Sum 3: The elements are {3}.

Sum 4: The elements are {1. 3}.

Sum 5: The elements are {1, 3, 1}.

Sum 6: The elements are {1, 5}.

Sum 7: The elements are {1, 5, 1}.

Sum 8: The elements are {3, 5}.

Sum 9: The elements are {1, 3, 5}.

Sum 10: The elements are {1, 3, 5, 1}.

Input: arr[] = {2, 6, 8, 12, 19}, K = 20
Output: 2

Approach: The given problem can be solved by sorting the array in increasing order and then try to make the sum value over the range [1, K] using the fact that if the sum of array elements X, then all the values over the range [1, X] can be formed. Otherwise, it is required to insert the value (sum + 1) as an array element. Follow the steps below to solve the problem:

Sort the array arr[] in increasing order.
Initialize the variable, say index as 0 to maintain the index of the array element and count as 0 to store the resultant total elements added.
If the value of arr[0] is greater than 1, then 1 needs to be appended, so increase the value of the count by 1. Otherwise, increase the value of the index by 1.
Initialize the variable, say expect as 2 to maintain the next value expected in the range from 1 to K to be formed from the array arr[].
Iterate a loop until the value of expect is at most K and perform the following steps:
- If the index is greater than equal to N or arr[index] is greater than the value of expect, then increase the value of count by 1 and multiply the value of expect by 2.
- Otherwise, increase the value of expect by arr[index] and increase the value of the index by 1.
After completing the above steps, print the value of count as the result.

Below is the implementation of the above approach.

C++14

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum number of elements that must
// be added to make the sum of array element over the range
// [1, K]
void findMinimumNumberOfElements(int n, int k, int arr[])
{
    // Sort the given array
    sort(arr, arr + n);
 
    // Stores the index for the array
    int index = 0, count = 0;
    // If 1 is not present, then append it
    if (arr[0] > 1)
        ++count;
    // Move on to next index
    else
        ++index;
 
    // The expected value in the array
    long long expect = 2;
    while (expect <= k) {
        // Need to append this number
        if (index >= n || arr[index] > expect) {
            ++count;
            expect += expect;
        }
 
        // Otherwise, expand the range by current number
        else {
            expect += arr[index];
            ++index;
        }
    }
    // Print the answer
    cout << count;
}
 
// Driver Code
int main()
{
    int arr[] = { 2, 6, 8, 12, 19 };
    int K = 20;
    int N = sizeof(arr) / sizeof(arr[0]);
    findMinimumNumberOfElements(N, K, arr);
 
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

C

// C program for the above approach
 
#include <stdio.h>
#include <stdlib.h>
 
int cmpfunc(const void* a, const void* b)
{
    return (*(int*)a - *(int*)b);
}
 
// Function to find the minimum number of elements that must
// be added to make the sum of array element over the range
// [1, K]
void findMinimumNumberOfElements(int n, int k, int arr[])
{
    // Sort the given array
    qsort(arr, n, sizeof(int), cmpfunc);
 
    // Stores the index for the array
    int index = 0, count = 0;
    // If 1 is not present, then append it
    if (arr[0] > 1)
        ++count;
    // Move on to next index
    else
        ++index;
 
    // The expected value in the array
    long long expect = 2;
    while (expect <= k) {
        // Need to append this number
        if (index >= n || arr[index] > expect) {
            ++count;
            expect += expect;
        }
 
        // Otherwise, expand the range by current number
        else {
            expect += arr[index];
            ++index;
        }
    }
    // Print the answer
    printf("%d", count);
}
 
// Driver Code
int main()
{
    int arr[] = { 2, 6, 8, 12, 19 };
    int K = 20;
    int N = sizeof(arr) / sizeof(arr[0]);
    findMinimumNumberOfElements(N, K, arr);
 
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Java

// Java program for the above approach
import java.io.*;
import java.util.Arrays;
 
class GFG {
 
    // Function to find the minimum number of elements that
    // must be added to make the sum of array element over
    // the range [1, K]
    static void findMinimumNumberOfElements(int n, int k, int[] arr)
    {
        // Sort the given array
        Arrays.sort(arr);
 
        // Stores the index for the array
        int index = 0, count = 0;
        // If 1 is not present, then append it
 
        if (arr[0] > 1)
            ++count;
        // Move on to next index
        else
            ++index;
 
        // The expected value in the array
        long expect = 2;
        while (expect <= k) {
 
            // Need to append this number
            if (index >= n || arr[index] > expect) {
                ++count;
                expect += expect;
            }
 
            // Otherwise, expand the range by current number
            else {
                expect += arr[index];
                ++index;
            }
        }
 
        // Print the answer
        System.out.println(count);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 2, 6, 8, 12, 19 };
        int K = 20;
        int N = arr.length;
        findMinimumNumberOfElements(N, K, arr);
    }
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Python3

# Python 3 program for the above approach
 
# Function to find the minimum number
# of elements that must be added to
# make the sum of array element over
# the range [1, K]
def findMinimumNumberOfElements(n, k, arr):
    # Sort the given array
    arr.sort()
 
    # Stores the index for the
    # array
    index = 0
    count = 0
 
    if (arr[0] > 1):
        # If 1 is not present, then
        # append it
        count += 1
 
    # Move on to next index
    else:
        index += 1
 
    # The expected value in the array
    expect = 2
    while (expect <= k):
 
        # Need to append this number
        if (index >= n or arr[index] > expect):
            count += 1
            expect += expect
 
        # Otherwise, expand the range
        # by current number
        else:
            expect += arr[index]
            index += 1
 
    # Print the answer
    print(count)
 
# Driver Code
if __name__ == '__main__':
    arr = [2, 6, 8, 12, 19]
    K = 20
    N = len(arr)
    findMinimumNumberOfElements(N, K, arr)
     
    # This code is contributed by ipg2016107.

C#

// C# program for the above approach
using System;
 
class GFG {
     
 // Function to find the minimum number
    // of elements that must be added to
    // make the sum of array element over
    // the range [1, K]
    static void findMinimumNumberOfElements(int n, int k,
                                            int[] arr)
    {
        // Sort the given array
        Array.Sort(arr);
 
        // Stores the index for the
        // array
        int index = 0;
        int count = 0;
 
        if (arr[0] > 1) {
 
            // If 1 is not present, then
            // append it
            ++count;
        }
 
        // Move on to next index
        else {
            ++index;
        }
 
        // The expected value in the array
        long expect = 2;
        while (expect <= k) {
 
            // Need to append this number
            if (index >= n || arr[index] > expect) {
                ++count;
                expect += expect;
            }
 
            // Otherwise, expand the range
            // by current number
            else {
                expect += arr[index];
                ++index;
            }
        }
 
        // Print the answer
        Console.WriteLine(count);
    }
     
    // Driver code
    public static void Main()
    {
        int[] arr = { 2, 6, 8, 12, 19 };
        int K = 20;
        int N = arr.Length;
        findMinimumNumberOfElements(N, K, arr);
    }
}
 
// This code is contributed by avijitmondal1998.

Javascript

<script>
// Javascript program for the above approach
 
// Function to find the minimum number
// of elements that must be added to
// make the sum of array element over
// the range [1, K]
function findMinimumNumberOfElements(n, k, arr) {
    // Sort the given array
    arr.sort((a, b) => a - b);
 
    // Stores the index for the
    // array
    let index = 0;
    let count = 0;
 
    if (arr[0] > 1) {
 
        // If 1 is not present, then
        // append it
        ++count;
    }
 
    // Move on to next index
    else {
        ++index;
    }
 
    // The expected value in the array
    let expect = 2;
    while (expect <= k) {
 
        // Need to append this number
        if (index >= n || arr[index] > expect) {
            ++count;
            expect += expect;
        }
 
        // Otherwise, expand the range
        // by current number
        else {
            expect += arr[index];
            ++index;
        }
    }
 
    // Print the answer
    document.write(count);
}
 
// Driver Code
 
let arr = [2, 6, 8, 12, 19];
let K = 20;
let N = arr.length;
findMinimumNumberOfElements(N, K, arr);
 
// This code is contributed by _saurabh_jaiswal.
</script>

Output:

Time Complexity: O(max(K, N*log N))
Auxiliary Space: O(1)

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 zambiatek!