Check if Array has 2 distinct subsequences where smaller one has higher Sum
Given an array A[] of N integers. Check if there exist 2 distinct sub-sequences X and Y of the given array, such that the sum of elements of X is greater than the sum of elements of Y, but the number of elements in X is less than the number of elements in Y.
Examples:
Input: N = 5, A[] = {2, 3, 8, 1, 6}
Output: YES
Explanation: Consider the sequences: X = {6}, Y = {2, 3}.
It can be easily seen that size of X(i.e. 1) < size of Y(i.e 2), whereas sum of elements of X (i.e 6) > sum of elements of Y(i.e 5).Input: N = 6, A[] = {1, 1, 1, 1, 1, 1}
Output: NO
Approach: The problem can be solved by using two pointer approach based on the following idea:
In a sorted array if the sum of first K (where K > N/2) smaller elements is less than the sum of the remaining elements then there can be such subsequences, otherwise not.
Follow the steps mentioned below to solve the problem:
- Sort the given array.
- Declare two variables beg and end to store the sum of elements from the beginning and the end of the sorted array.
- Initialize beg with arr[0] and end with 0 because there should be at least 1 element more in the subsequence with less sum.
- Use two pointers from i = 1 and j = N-1:
- Add arr[i] with beg and arr[j] with end.
- If beg is less than end, then break the iteration. Because it is possible to find such subsequences as all the other elements on the higher side is bigger than the first half and the lower sides have already one more element.
- If after the total iteration no such sequence is found, return it is not possible.
Below is the implementation of the above approach:
C++
// C++ Code for above approach #include <bits/stdc++.h> using namespace std; // Function to check if the given // array have 2 distinct subsequences // such that number of elements in one // having greater sum is less bool haveSubsequences( int N, int A[]) { // Sorting the given sequence Array sort(A, A + N); // Variable "beg" stores the sum of // elements from beginning variable // "end" stores the sum of elements // from end int beg = A[0], end = 0; // Flag variable to check for wrong // answer int flag = 0; // Initializing 2 pointers int i = 1, j = N - 1; // Iterating array from both sides // via 2 pointers and checking if // sum of starting say k+1 elements is // less than sum of k elements from the // end while (i < j) { beg += A[i]; end += A[j]; // If sum of starting i elements is // less than the sum of j elements, // we make flag 1 and break the loop if (beg < end) { flag = 1; break ; } // Else we simply increment i and // decrement j i++; j--; } // Returning true or false in accordance // with the flag if (flag == 1) { return true ; } else { return false ; } } // Driver Code int main() { int N = 5; int A[] = { 2, 3, 8, 1, 6 }; bool answer = haveSubsequences(N, A); if (answer == true ) { cout << "YES" ; } else { cout << "NO" ; } } |
Java
/*package whatever //do not write package name here */ import java.io.*; import java.lang.*; import java.util.*; class GFG { // Function to check if the given // array have 2 distinct subsequences // such that number of elements in one // having greater sum is less public static boolean haveSubsequences( int N, int A[]) { // Sorting the given sequence Array Arrays.sort(A); // Variable "beg" stores the sum of // elements from beginning variable // "end" stores the sum of elements // from end int beg = A[ 0 ], end = 0 ; // Flag variable to check for wrong // answer int flag = 0 ; // Initializing 2 pointers int i = 1 , j = N - 1 ; // Iterating array from both sides // via 2 pointers and checking if // sum of starting say k+1 elements is // less than sum of k elements from the // end while (i < j) { beg += A[i]; end += A[j]; // If sum of starting i elements is // less than the sum of j elements, // we make flag 1 and break the loop if (beg < end) { flag = 1 ; break ; } // Else we simply increment i and // decrement j i++; j--; } // Returning true or false in accordance // with the flag if (flag == 1 ) { return true ; } else { return false ; } } // Driver Code public static void main(String[] args) { int N = 5 ; int A[] = { 2 , 3 , 8 , 1 , 6 }; boolean answer = haveSubsequences(N, A); if (answer == true ) { System.out.println( "YES" ); } else { System.out.println( "NO" ); } } } // This code is contributed by amnindersingh1414. |
Python3
# Python Code for above approach # Function to check if the given # array have 2 distinct subsequences # such that number of elements in one # having greater sum is less def haveSubsequences(N, A): # Sorting the given sequence Array A.sort() # Variable "beg" stores the sum of # elements from beginning variable # "end" stores the sum of elements # from end beg = A[ 0 ] end = 0 # Flag variable to check for wrong # answer flag = 0 # Initializing 2 pointers i = 1 j = N - 1 # Iterating array from both sides # via 2 pointers and checking if # sum of starting say k+1 elements is # less than sum of k elements from the # end while i < j: beg + = A[i] end + = A[j] # If sum of starting i elements is # less than the sum of j elements, # we make flag 1 and break the loop if (beg < end): flag = 1 break # Else we simply increment i and # decrement j i + = 1 j - = 1 # Returning true or false in accordance # with the flag if (flag = = 1 ): return True else : return False # Driver Code if __name__ = = '__main__' : N = 5 A = [ 2 , 3 , 8 , 1 , 6 ] answer = haveSubsequences(N, A) if (answer = = True ): print ( "YES" ) else : print ( "NO" ) # This code is contributed by amnindersingh1414. |
C#
// C# program for the above approach using System; class GFG { // Function to check if the given // array have 2 distinct subsequences // such that number of elements in one // having greater sum is less static bool haveSubsequences( int N, int []A) { // Sorting the given sequence Array Array.Sort(A); // Variable "beg" stores the sum of // elements from beginning variable // "end" stores the sum of elements // from end int beg = A[0], end = 0; // Flag variable to check for wrong // answer int flag = 0; // Initializing 2 pointers int i = 1, j = N - 1; // Iterating array from both sides // via 2 pointers and checking if // sum of starting say k+1 elements is // less than sum of k elements from the // end while (i < j) { beg += A[i]; end += A[j]; // If sum of starting i elements is // less than the sum of j elements, // we make flag 1 and break the loop if (beg < end) { flag = 1; break ; } // Else we simply increment i and // decrement j i++; j--; } // Returning true or false in accordance // with the flag if (flag == 1) { return true ; } else { return false ; } } // Driver Code public static void Main() { int N = 5; int []A = { 2, 3, 8, 1, 6 }; bool answer = haveSubsequences(N, A); if (answer == true ) { Console.WriteLine( "YES" ); } else { Console.WriteLine( "NO" ); } } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript Code for above approach // Function to check if the given // array have 2 distinct subsequences // such that number of elements in one // having greater sum is less const haveSubsequences = (N, A) => { // Sorting the given sequence Array A.sort(); // Variable "beg" stores the sum of // elements from beginning variable // "end" stores the sum of elements // from end let beg = A[0], end = 0; // Flag variable to check for wrong // answer let flag = 0; // Initializing 2 pointers let i = 1, j = N - 1; // Iterating array from both sides // via 2 pointers and checking if // sum of starting say k+1 elements is // less than sum of k elements from the // end while (i < j) { beg += A[i]; end += A[j]; // If sum of starting i elements is // less than the sum of j elements, // we make flag 1 and break the loop if (beg < end) { flag = 1; break ; } // Else we simply increment i and // decrement j i++; j--; } // Returning true or false in accordance // with the flag if (flag == 1) { return true ; } else { return false ; } } // Driver Code let N = 5; let A = [2, 3, 8, 1, 6]; let answer = haveSubsequences(N, A); if (answer == true ) { document.write( "YES" ); } else { document.write( "NO" ); } // This code is contributed by rakeshsahni </script> |
YES
Time Complexity: O(N*log(N))
Auxiliary Space: O(1)
Another Approach:
- Initialize four variables – smallest, second_smallest, largest, and second_largest – to the maximum and minimum values possible for integers.
- Traverse the given array from the first element to the last element:
a. If the current element is smaller than the smallest value seen so far, update the smallest and second_smallest variables accordingly.
b. If the current element is between the smallest and second_smallest values seen so far, update the second_smallest variable.
c. If the current element is larger than the largest value seen so far, update the largest and second_largest variables accordingly.
d. If the current element is between the largest and second_largest values seen so far, update the second_largest variable. - After the traversal, compare the sum of the largest and second_smallest variables with the sum of the second_largest and smallest variables:
a. If the former is greater than the latter, return true.
b. Otherwise, return false. - End of the function.
Below is the implementation of the above approach:
C++
// C++ Code for above approach #include <bits/stdc++.h> using namespace std; // Function to check if the given // array have 2 distinct subsequences // such that number of elements in one // having greater sum is less bool haveSubsequences( int N, int A[]) { // Variables to store smallest and // second smallest elements seen so far int smallest = INT_MAX, second_smallest = INT_MAX; // Variables to store largest and // second largest elements seen so far int largest = INT_MIN, second_largest = INT_MIN; // Traverse the array and update the // variables accordingly for ( int i = 0; i < N; i++) { if (A[i] < smallest) { second_smallest = smallest; smallest = A[i]; } else if (A[i] < second_smallest) { second_smallest = A[i]; } if (A[i] > largest) { second_largest = largest; largest = A[i]; } else if (A[i] > second_largest) { second_largest = A[i]; } } // Check if the sum of the largest and // second smallest elements is greater // than the sum of the second largest // and smallest elements if (largest + second_smallest > second_largest + smallest) { return true ; } else { return false ; } } // Driver Code int main() { int N = 5; int A[] = { 2, 3, 8, 1, 6 }; bool answer = haveSubsequences(N, A); if (answer == true ) { cout << "YES" ; } else { cout << "NO" ; } } |
Java
import java.util.*; public class Main { // Function to check if the given // array have 2 distinct subsequences // such that number of elements in one // having greater sum is less public static boolean haveSubsequences( int N, int A[]) { // Variables to store smallest and // second smallest elements seen so far int smallest = Integer.MAX_VALUE, second_smallest = Integer.MAX_VALUE; // Variables to store largest and // second largest elements seen so far int largest = Integer.MIN_VALUE, second_largest = Integer.MIN_VALUE; // Traverse the array and update the // variables accordingly for ( int i = 0 ; i < N; i++) { if (A[i] < smallest) { second_smallest = smallest; smallest = A[i]; } else if (A[i] < second_smallest) { second_smallest = A[i]; } if (A[i] > largest) { second_largest = largest; largest = A[i]; } else if (A[i] > second_largest) { second_largest = A[i]; } } // Check if the sum of the largest and // second smallest elements is greater // than the sum of the second largest // and smallest elements if (largest + second_smallest > second_largest + smallest) { return true ; } else { return false ; } } // Driver Code public static void main(String[] args) { int N = 5 ; int A[] = { 2 , 3 , 8 , 1 , 6 }; boolean answer = haveSubsequences(N, A); if (answer == true ) { System.out.println( "YES" ); } else { System.out.println( "NO" ); } } } |
Python
def haveSubsequences(N, A): # Variables to store smallest and # second smallest elements seen so far smallest = float ( 'inf' ) second_smallest = float ( 'inf' ) # Variables to store largest and # second largest elements seen so far largest = float ( '-inf' ) second_largest = float ( '-inf' ) # Traverse the array and update the # variables accordingly for i in range (N): if A[i] < smallest: second_smallest = smallest smallest = A[i] elif A[i] < second_smallest: second_smallest = A[i] if A[i] > largest: second_largest = largest largest = A[i] elif A[i] > second_largest: second_largest = A[i] # Check if the sum of the largest and # second smallest elements is greater # than the sum of the second largest # and smallest elements if largest + second_smallest > second_largest + smallest: return True else : return False # Driver Code N = 5 A = [ 2 , 3 , 8 , 1 , 6 ] answer = haveSubsequences(N, A) if answer: print ( "YES" ) else : print ( "NO" ) |
C#
using System; class GFG { // Function to check if the given // array have 2 distinct subsequences // such that number of elements in one // having greater sum is less public static bool HaveSubsequences( int N, int [] A) { // Variables to store smallest and // second smallest elements seen so far int smallest = int .MaxValue, second_smallest = int .MaxValue; // Variables to store largest and // second largest elements seen so far int largest = int .MinValue, second_largest = int .MinValue; // Traverse the array and update the // variables accordingly for ( int i = 0; i < N; i++) { if (A[i] < smallest) { second_smallest = smallest; smallest = A[i]; } else if (A[i] < second_smallest) { second_smallest = A[i]; } if (A[i] > largest) { second_largest = largest; largest = A[i]; } else if (A[i] > second_largest) { second_largest = A[i]; } } // Check if the sum of the largest and // second smallest elements is greater // than the sum of the second largest // and smallest elements if (largest + second_smallest > second_largest + smallest) { return true ; } else { return false ; } } // Driver Code public static void Main( string [] args) { int N = 5; int [] A = new int [] { 2, 3, 8, 1, 6 }; bool answer = HaveSubsequences(N, A); if (answer == true ) { Console.WriteLine( "YES" ); } else { Console.WriteLine( "NO" ); } } } |
Javascript
// Function to check if the given // array have 2 distinct subsequences // such that number of elements in one // having greater sum is less function haveSubsequences(N, A) { // Variables to store smallest and // second smallest elements seen so far let smallest = Number.MAX_SAFE_INTEGER; let second_smallest = Number.MAX_SAFE_INTEGER; // Variables to store largest and // second largest elements seen so far let largest = Number.MIN_SAFE_INTEGER; let second_largest = Number.MIN_SAFE_INTEGER; // Traverse the array and update the // variables accordingly for (let i = 0; i < N; i++) { if (A[i] < smallest) { second_smallest = smallest; smallest = A[i]; } else if (A[i] < second_smallest) { second_smallest = A[i]; } if (A[i] > largest) { second_largest = largest; largest = A[i]; } else if (A[i] > second_largest) { second_largest = A[i]; } } // Check if the sum of the largest and // second smallest elements is greater // than the sum of the second largest // and smallest elements if (largest + second_smallest > second_largest + smallest) { return true ; } else { return false ; } } // Driver code const N = 5; const A = [2, 3, 8, 1, 6]; const answer = haveSubsequences(N, A); if (answer === true ) { console.log( "YES" ); } else { console.log( "NO" ); } |
YES
Time complexity: O(n)
Auxiliary Space: O(1)
Contact Us