Check whether a subsequence exists with sum equal to k if arr[i]> 2*arr[i-1]
Given a sorted array of positive integers where arr[i] > 2*arr[i-1], check whether a sub sequence exists whose sum is equal to k.
Examples:
Input : arr[]={ 1, 3, 7, 15, 31}, K=18
Output :True
A[1] + A[3] = 3 + 15 = 18
We found a subsequence whose sum is 18
Input :arr[]={ 1, 3, 7, 15, 31}, K=20
Output :False
No subsequence can be found with sum 20
Naive Solution: The basic solution is to check for all the 2^n possible combinations and check if there is any subsequence whose sum is equal to K. This process will not work for higher values of N, N>20.
Time Complexity: O(2^N)
Efficient Solution: We are given arr[i] >2*arr[i-1] so we can say that arr[i] > ( arr[i-1] + arr[i-2] + …+ arr[2] + arr[1] + arr[0] ).
Let us assume that arr[i] <= K ( arr[i-1] + arr[i-2] + …+ arr[2] + arr[1] + arr[0] ) ), so we have to include arr[i] in the set . So, we have to traverse the array in descending order and when we find arr[i]<=k, we will include arr[i] in the set and subtract arr[i] from K and continue the loop until value of K is equal to zero.
If the value of K is zero then there is a subsequence else not.
Below is the Implementation of above approach:
C++
// C++ implementation of above approach #include <iostream> using namespace std; // Function to check whether sum of any set // of the array element is equal // to k or not bool CheckForSequence( int arr[], int n, int k) { // Traverse the array from end // to start for ( int i = n - 1; i >= 0; i--) { // if k is greater than // arr[i] then subtract // it from k if (k >= arr[i]) k -= arr[i]; } // If there is any subsequence // whose sum is equal to k if (k != 0) return false ; else return true ; } // Driver code int main() { int A[] = { 1, 3, 7, 15, 31 }; int n = sizeof (A) / sizeof ( int ); cout << (CheckForSequence(A, n, 18) ? "True" : "False" ) << endl; return 0; } |
Java
// Java implementation of above approach import java.io.*; class GFG { // Function to check whether // sum of any set of the array element // is equal to k or not static boolean CheckForSequence( int arr[], int n, int k) { // Traverse the array from end // to start for ( int i = n - 1 ; i >= 0 ; i--) { // if k is greater than // arr[i] then subtract // it from k if (k >= arr[i]) k -= arr[i]; } // If there is any subsequence // whose sum is equal to k if (k != 0 ) return false ; else return true ; } // Driver code public static void main (String[] args) { int A[] = { 1 , 3 , 7 , 15 , 31 }; int n = A.length; System.out.println(CheckForSequence(A, n, 18 ) ? "True" : "False" ); } } // This code is contributed by jit_t |
Python3
# Python3 implementation of above approach # Function to check whether sum of any set # of the array element is equal # to k or not def CheckForSequence(arr, n, k) : # Traverse the array from end # to start for i in range (n - 1 , - 1 , - 1 ) : # if k is greater than # arr[i] then subtract # it from k if (k > = arr[i]) : k - = arr[i]; # If there is any subsequence # whose sum is equal to k if (k ! = 0 ) : return False ; else : return True ; # Driver code if __name__ = = "__main__" : A = [ 1 , 3 , 7 , 15 , 31 ]; n = len (A); if (CheckForSequence(A, n, 18 )) : print ( True ) else : print ( False ) # This code is contributed by AnkitRai01 |
C#
// C# implementation of above approach using System; class GFG { // Function to check whether // sum of any set of the array element // is equal to k or not static bool CheckForSequence( int []arr, int n, int k) { // Traverse the array from end // to start for ( int i = n - 1; i >= 0; i--) { // if k is greater than // arr[i] then subtract // it from k if (k >= arr[i]) k -= arr[i]; } // If there is any subsequence // whose sum is equal to k if (k != 0) return false ; else return true ; } // Driver code public static void Main () { int []A = { 1, 3, 7, 15, 31 }; int n = A.Length; Console.WriteLine(CheckForSequence(A, n, 18) ? "True" : "False" ); } } // This code is contributed by anuj_67.. |
Javascript
<script> // Javascript program to implement the above approach // Function to check whether sum of any set // of the array element is equal // to k or not function CheckForSequence( arr,n,k) { // Traverse the array from end // to start for ( var i = n - 1; i >= 0; i--) { // if k is greater than // arr[i] then subtract // it from k if (k >= arr[i]) k -= arr[i]; } // If there is any subsequence // whose sum is equal to k if (k != 0) return false ; else return true ; } var A = [ 1, 3, 7, 15, 31 ]; var n = A.length; document.write( (CheckForSequence(A, n, 18) ? "True" : "False" ) + "<br>" ); //This code is contributed by SoumikModnal </script> |
True
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us