Given an array arr[] consisting of N positive integers and a positive integer K, The task is to find a subsequence of an array arr[] whose sum of the elements is in the range [(K+1)/2, K]. If there is a subsequence then print the indices of the subsequence, otherwise print -1.
Note: There can be multiple answers possible for this problem, print any one of them.
Examples:
Input: arr[ ] = {6, 2, 20, 3, 5, 6}, K = 13
Output: 0 1 3
Explanation:
Sum of elements of the subsequence {6, 2, 3} is 11 that is in the range[(K+1)/2, K].Input: arr[ ] = {20, 24, 33, 100}, K = 2
Output: -1
Approach: This problem can be solved by traversing over the array arr[ ]. Follow the steps below to solve this problem:
- Initialize a vector ans to store indices of the resultant subsequence and totalSum to store the sum of elements of the subsequence.
- Iterate in the range [0, N-1] using the variable i and perform the following steps:
- If arr[i] > K, continue traversing the elements of the array.
- If arr[i] is in the range [(K+1)/2, K], then return the index of the current element as the answer and terminate the loop.
- If arr[i] +totalSum is less than K, then add the current element to totalSum and add index i in vector ans.
- If the totalSum is not in the given range then print -1, Otherwise print the vector ans.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find a subsequence of the // given array whose sum of the elements // is in range [K+1/2, K] void isSumOfSubSeqInRange( int arr[], int n, int k) { // Vector to store the subsequence indices vector< int > ans; // Variable to store the sum of subsequence int totalSum = 0; for ( int i = 0; i < n; i++) { // If the current element is // greater than K then move // forward if (arr[i] > k) { continue ; } // If the current element is in // the given range if (arr[i] >= (k + 1) / 2) { ans.clear(); ans.push_back(i); totalSum = arr[i]; break ; } // If current element and totalSum // is less than K else if (arr[i] + totalSum <= k) { totalSum += arr[i]; ans.push_back(i); } } // Checking if the totalSum is not // in the given range then print -1 if (2 * totalSum < k) { cout << -1 << endl; return ; } // Otherwise print the answer for ( int x : ans) { cout << x << " " ; } cout << endl; } // Driver Code int main() { // Given Input int arr[] = { 6, 2, 20, 3, 5, 6 }; int N = 6; int K = 13; // Function Call isSumOfSubSeqInRange(arr, N, K); return 0; } |
Java
// Java program for the above approach import java.util.Vector; public class GFG { // Function to find a subsequence of the // given array whose sum of the elements // is in range [K+1/2, K] static void isSumOfSubSeqInRange( int arr[], int n, int k) { // Vector to store the subsequence indices Vector<Integer> ans = new Vector<>(); // Variable to store the sum of subsequence int totalSum = 0 ; for ( int i = 0 ; i < n; i++) { // If the current element is // greater than K then move // forward if (arr[i] > k) { continue ; } // If the current element is in // the given range if (arr[i] >= (k + 1 ) / 2 ) { ans.clear(); ans.add(i); totalSum = arr[i]; break ; } // If current element and totalSum // is less than K else if (arr[i] + totalSum <= k) { totalSum += arr[i]; ans.add(i); } } // Checking if the totalSum is not // in the given range then print -1 if ( 2 * totalSum < k) { System.out.println(- 1 ); return ; } // Otherwise print the answer for ( int x : ans) { System.out.print(x + " " ); } System.out.println(); } // Driver code public static void main(String[] args) { // Given Input int arr[] = { 6 , 2 , 20 , 3 , 5 , 6 }; int N = 6 ; int K = 13 ; // Function Call isSumOfSubSeqInRange(arr, N, K); } } // This code is contributed by abhinavjain194 |
Python3
# Python3 program for the above approach # Function to find a subsequence of the # given array whose sum of the elements # is in range [K+1/2, K] def isSumOfSubSeqInRange(arr, n, k): # Vector to store the subsequence indices ans = [] # Variable to store the sum of subsequence totalSum = 0 for i in range (n): # If the current element is # greater than K then move # forward if (arr[i] > k): continue # If the current element is in # the given range if (arr[i] > = (k + 1 ) / 2 ): ans.clear() ans.append(i) totalSum = arr[i] break # If current element and totalSum # is less than K elif (arr[i] + totalSum < = k): totalSum + = arr[i] ans.append(i) # Checking if the totalSum is not # in the given range then print -1 if ( 2 * totalSum < k): print ( - 1 ) return # Otherwise print the answer for x in ans: print (x, end = " " ) # Driver Code if __name__ = = '__main__' : # Given Input arr = [ 6 , 2 , 20 , 3 , 5 , 6 ] N = 6 K = 13 # Function Call isSumOfSubSeqInRange(arr, N, K) # This code is contributed by bgangwar59 |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { // Function to find a subsequence of the // given array whose sum of the elements // is in range [K+1/2, K] static void isSumOfSubSeqInRange( int [] arr, int n, int k) { // Vector to store the subsequence indices List< int > ans = new List< int >(); // Variable to store the sum of subsequence int totalSum = 0; for ( int i = 0; i < n; i++) { // If the current element is // greater than K then move // forward if (arr[i] > k) { continue ; } // If the current element is in // the given range if (arr[i] >= (k + 1) / 2) { ans.Clear(); ans.Add(i); totalSum = arr[i]; break ; } // If current element and totalSum // is less than K else if (arr[i] + totalSum <= k) { totalSum += arr[i]; ans.Add(i); } } // Checking if the totalSum is not // in the given range then print -1 if (2 * totalSum < k) { Console.WriteLine(-1); return ; } // Otherwise print the answer foreach ( int x in ans) { Console.Write(x + " " ); } Console.WriteLine(); } // Driver code static public void Main () { // Given Input int [] arr = { 6, 2, 20, 3, 5, 6 }; int N = 6; int K = 13; // Function Call isSumOfSubSeqInRange(arr, N, K); } } // This Code is contributed by ShubhamSingh10 |
Javascript
<script> // Javascript program for the above approach // Function to find a subsequence of the // given array whose sum of the elements // is in range [K+1/2, K] function isSumOfSubSeqInRange(arr, n, k) { // Vector to store the subsequence indices let ans = []; // Variable to store the sum of subsequence let totalSum = 0; for (let i = 0; i < n; i++) { // If the current element is // greater than K then move // forward if (arr[i] > k) { continue ; } // If the current element is in // the given range if (arr[i] >= (k + 1) / 2) { ans = []; ans.push(i); totalSum = arr[i]; break ; } // If current element and totalSum // is less than K else if (arr[i] + totalSum <= k) { totalSum += arr[i]; ans.push(i); } } // Checking if the totalSum is not // in the given range then print -1 if (2 * totalSum < k) { document.write(-1 + "<br>" ); return ; } // Otherwise print the answer for (let x of ans) { document.write(x + " " ); } document.write( "<br>" ); } // Driver Code // Given Input let arr = [6, 2, 20, 3, 5, 6]; let N = 6; let K = 13; // Function Call isSumOfSubSeqInRange(arr, N, K); // This code is contributed by gfgking. </script> |
0 1 3
Time complexity: O(N)
Auxiliary space: O(N)