Check if given Array can be formed from initial Array having one element
Given array A[], the task for this problem is to check whether A[] can be formed from array B[] = {1} by performing the following operation any number of times, select a subsequence of B[] and insert total sum of this subsequence in B[] to any position. Print “YES” if it is possible “NO otherwise.
Examples:
Input: A[] = {5, 1, 3, 2, 1}
Output: YES
Explanation:
- Initially, B[] = [1]
- Choosing the subsequence [1] and inserting 1 in the array B[], B[] changes to [1, 1].
- Choosing the subsequence [1, 1] and inserting 1+1 = 2 in the middle of the array B[], B[] changes to [1, 2, 1].
- Choosing the subsequence [1, 2] and inserting 1+2 = 3 after the first 1 of the array B[], B[] changes to [1, 3, 2, 1].
- Choosing the subsequence [1, 3, 1] and inserting 1+3+1 = 5 at the beginning of the array B[], B[] changes to [5, 1, 3, 2, 1]
which is the array we needed to obtain.
Input: A[] = {7, 1, 5, 2, 1}
Output: NO
Approach: To solve the problem follow the below idea:
Priority Queue can be used to solve this problem. Observation is that it is possible construct given array stepwise in ascending order, if sum of all other elements present in B[] is greater than new element that is to be added.
Below are the steps for the above approach:
- Create a priority queue and insert all elements of array A[] in that priority queue.
- Create variable curSum = 1.
- If the first element of the priority queue is not 1 then return “NO”.
- Else erase the first element of the priority queue. Run a while loop until the priority queue becomes empty and store the first element of the priority queue in variable FIRST and then erase the first element of the priority queue. if FIRST is greater than curSum the return “NO” else add FIRST to curSum. If while loop ends return “YES”.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach: #include <bits/stdc++.h> using namespace std; // Function to check whether given array // A[] can be formed from B[] = {1} by // performing given operation string isPossible( int A[], int N) { // multiset multiset< int > ms; // Inserting all the elements // in our multiset for ( int i = 0; i < N; i++) { ms.insert(A[i]); } // Variable for total current sum int curSum = 1; // First element has to be 1 if (*ms.begin() == 1) { // Deleting first element ms.erase(ms.begin()); // Run while loop until multiset // becomes empty while (ms.size()) { // First element of multiset // storing in variable first int first = *ms.begin(); // Erase first element // of multiset ms.erase(ms.begin()); // If curSum is grater than // our first element if (curSum >= first) curSum += first; // B[] can not be transformed // into A[] else return "NO" ; } // B[] can be transformed // into A[] return "YES" ; } // Case when answer is not possible else return "NO" ; } // Driver Code int32_t main() { // Input 1 int N = 5; int A[] = { 5, 1, 3, 2, 1 }; // Function Call cout << isPossible(A, N) << endl; // Input 2 int N1 = 5; int A1[] = { 7, 1, 5, 2, 1 }; // Function Call cout << isPossible(A1, N1) << endl; return 0; } |
Java
import java.util.ArrayList; import java.util.Collections; public class GFG { public static void main(String[] args) { int N = 5 ; int [] A = { 5 , 1 , 3 , 2 , 1 }; System.out.println(isPossible(A, N)); int N1 = 5 ; int [] A1 = { 7 , 1 , 5 , 2 , 1 }; System.out.println(isPossible(A1, N1)); } public static String isPossible( int [] A, int N) { ArrayList<Integer> ms = new ArrayList<>(); for ( int i = 0 ; i < N; i++) { ms.add(A[i]); } Collections.sort(ms); int curSum = 1 ; if (ms.get( 0 ) == 1 ) { ms.remove( 0 ); while (!ms.isEmpty()) { int first = ms.get( 0 ); ms.remove( 0 ); if (curSum >= first) { curSum += first; } else { return "NO" ; } } return "YES" ; } else { return "NO" ; } } } |
Python3
# Python Implementation def isPossible(A, N): # List to keep track of elements ms = [] # Inserting all the elements in our list for i in range (N): ms.append(A[i]) ms.sort() # Variable for total current sum curSum = 1 # First element has to be 1 if ms[ 0 ] = = 1 : # Deleting the first element ms.pop( 0 ) # Run while loop until list becomes empty while ms: # First element of list storing in variable first first = ms[ 0 ] # Erase first element of list ms.pop( 0 ) # If curSum is greater than or equal to our first element if curSum > = first: curSum + = first # B[] cannot be transformed into A[] else : return "NO" # B[] can be transformed into A[] return "YES" # Case when answer is not possible else : return "NO" # Driver Code # Input 1 N = 5 A = [ 5 , 1 , 3 , 2 , 1 ] # Function Call print (isPossible(A, N)) # Input 2 N1 = 5 A1 = [ 7 , 1 , 5 , 2 , 1 ] # Function Call print (isPossible(A1, N1)) # This code is contributed by Vaibhav Nandan |
C#
using System; using System.Collections.Generic; public class Program { public static string IsPossible(List< int > A, int N) { // List to keep track of elements List< int > ms = new List< int >(); // Inserting all the elements in our list for ( int i = 0; i < N; i++) { ms.Add(A[i]); } ms.Sort(); // Variable for total current sum int curSum = 1; // First element has to be 1 if (ms[0] == 1) { // Deleting the first element ms.RemoveAt(0); // Run while loop until list becomes empty while (ms.Count > 0) { // First element of list storing in variable first int first = ms[0]; // Erase first element of list ms.RemoveAt(0); // If curSum is greater than or equal to our first element if (curSum >= first) { curSum += first; } // B[] cannot be transformed into A[] else { return "NO" ; } } // B[] can be transformed into A[] return "YES" ; } // Case when answer is not possible else { return "NO" ; } } // Driver Code public static void Main( string [] args) { int N = 5; List< int > A = new List< int > {5, 1, 3, 2, 1}; Console.WriteLine(IsPossible(A, N)); int N1 = 5; List< int > A1 = new List< int > {7, 1, 5, 2, 1}; Console.WriteLine(IsPossible(A1, N1)); } } |
Javascript
// Function to check whether given array // A[] can be formed from B[] = {1} by // performing the given operation function isPossible(A, N) { // List to keep track of elements let ms = []; // Inserting all the elements in our list for (let i = 0; i < N; i++) { ms.push(A[i]); } ms.sort(); // Variable for total current sum let curSum = 1; // First element has to be 1 if (ms[0] === 1) { // Deleting the first element ms.shift(); // Run while loop until list becomes empty while (ms.length > 0) { // First element of list storing in variable first let first = ms[0]; // Erase first element of list ms.shift(); // If curSum is greater than or equal to our first element if (curSum >= first) { curSum += first; } else { // B[] cannot be transformed into A[] return "NO" ; } } // B[] can be transformed into A[] return "YES" ; } else { // Case when the answer is not possible return "NO" ; } } // Driver Code // Input 1 let N = 5; let A = [5, 1, 3, 2, 1]; // Function Call console.log(isPossible(A, N)); // Input 2 let N1 = 5; let A1 = [7, 1, 5, 2, 1]; // Function Call console.log(isPossible(A1, N1)); |
YES NO
Time Complexity: O(N*logN)
Auxiliary Space: O(N)
Related Articles:
Contact Us