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 Codeint 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 Codeint 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 approachimport 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 Codeif __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 approachusing 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 Codelet 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:
2
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
