Given an array input[] consisting only of 1s initially and an array target[] of size N, the task is to check if the array input[] can be converted to target[] by replacing input[i] with the sum of array elements in each step. If found to be true, then print “YES”. Otherwise, print “NO”.
Examples:
Input: input[] = { 1, 1, 1 }, target[] = { 9, 3, 5 }
Output: YES
Explanation:
Replacing input[1] with (input[0] + input[1] + input[2]) modifies input[] to { 1, 3, 1 }
Replacing input[2] with (input[0] + input[1] + input[2]) modifies input[] to { 1, 3, 5 }
Replacing input[0] with (input[0] + input[1] + input[2]) modifies input[] to { 9, 3, 5 }
Since the array input[] equal to the target[] array, the required output is “YES”.Input: input[] = { 1, 1, 1, 1 }, target[] = { 1, 1, 1, 2 }
Output: NO
Approach: The problem can be solved using Greedy technique. The idea is to always decrement the largest element of target[] array by the sum of the remaining array elements and check if the largest element of the target[]. If found to be true then print “YES”. Otherwise, print “NO”. Following are the observations:
If target[] = { 9, 3, 5 } and input[] = { 1, 1, 1 }
Decrementing target[0] by (target[1] + target[2]) modifies target[] to { 1, 3, 5 }
Decrementing target[2] by (target[0] + target[1]) modifies target[] to { 1, 3, 1 }
Decrementing target[1] by (target[0] + target[2]) modifies target[] to { 1, 1, 1 }
Since input[] array and target[] equal, the required output is YES.
- If the largest element in the array target[] is less than 1, then print “NO”.
- If the largest element in the array target[] is equal to 1, then print “YES”.
- Otherwise, decrement the largest element in the array target[] by the sum of remaining elements present in the array target[] while the largest element of the array is greater than 1.
Below is the implementation of the above approach:
C++
// CPP program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to check if the arr[] can be// converted to target[] by replacing// any element in arr[] by the sum of arr[]bool isPossible(int target[], int n){ // Store the maximum element int max = 0; // Store the index of // the maximum element int index = 0; // Traverse the array target[] for (int i = 0; i < n; i++) { // If current element is // greater than max if (max < target[i]) { max = target[i]; index = i; } } // If max element is 1 if (max == 1) return true; // Traverse the array, target[] for (int i = 0; i < n; i++) { // If current index is not equal to // maximum element index if (i != index) { // Update max max -= target[i]; // If max is less than // or equal to 0, if (max <= 0) return false; } } // Update the maximum element target[index] = max; // Recursively call the function return isPossible(target,n);}// Driver Codeint main(){ int target[] = { 9, 3, 5 }; // Size of the array int n = sizeof(target) / sizeof(target[0]); bool res = isPossible(target,n); if (res) { cout << "YES"; } else { cout << "NO"; } return 0;}// This code is contributed by 29AjayKumar |
Java
// Java program to implement// the above approachimport java.io.*;import java.util.*;class GFG { // Function to check if the arr[] can be // converted to target[] by replacing // any element in arr[] by the sum of arr[] public static boolean isPossible(int[] target) { // Store the maximum element int max = 0; // Store the index of // the maximum element int index = 0; // Traverse the array target[] for (int i = 0; i < target.length; i++) { // If current element is // greater than max if (max < target[i]) { max = target[i]; index = i; } } // If max element is 1 if (max == 1) return true; // Traverse the array, target[] for (int i = 0; i < target.length; i++) { // If current index is not equal to // maximum element index if (i != index) { // Update max max -= target[i]; // If max is less than // or equal to 0, if (max <= 0) return false; } } // Update the maximum element target[index] = max; // Recursively call the function return isPossible(target); } // Driver Code public static void main(String[] args) { int[] target = { 9, 3, 5 }; boolean res = isPossible(target); if (res) { System.out.println("YES"); } else { System.out.println("NO"); } }} |
Python3
# Python program to implement the above approach# Function to check if the arr[] can be# converted to target[] by replacing# any element in arr[] by the sum of arr[]def isPossible(target): # Store the maximum element max = 0 # Store the index of # the maximum element index = 0 # Traverse the array target[] for i in range(len(target)): # If current element is # greater than max if (max < target[i]): max = target[i] index = i # If max element is 1 if (max == 1): return True # Traverse the array, target[] for i in range(len(target)): # If current index is not equal to # maximum element index if (i != index): # Update max max -= target[i] # If max is less than # or equal to 0, if (max <= 0): return False # Update the maximum element target[index] = max # Recursively call the function return isPossible(target)# Driver Codetarget = [ 9, 3, 5 ]res = isPossible(target)if (res): print("YES")else: print("NO") # This code is contributed by RohitSingh07052. |
C#
// C# program for the above approachusing System;class GFG{ // Function to check if the arr[] can be // converted to target[] by replacing // any element in arr[] by the sum of arr[] public static bool isPossible(int[] target) { // Store the maximum element int max = 0; // Store the index of // the maximum element int index = 0; // Traverse the array target[] for (int i = 0; i < target.Length; i++) { // If current element is // greater than max if (max < target[i]) { max = target[i]; index = i; } } // If max element is 1 if (max == 1) return true; // Traverse the array, target[] for (int i = 0; i < target.Length; i++) { // If current index is not equal to // maximum element index if (i != index) { // Update max max -= target[i]; // If max is less than // or equal to 0, if (max <= 0) return false; } } // Update the maximum element target[index] = max; // Recursively call the function return isPossible(target); } // Driver Codestatic public void Main(){ int[] target = { 9, 3, 5 }; bool res = isPossible(target); if (res) { Console.WriteLine("YES"); } else { Console.WriteLine("NO"); } }}// This code is contributed by jana_sayantan. |
Javascript
<script>// javascript program to implement// the above approach// Function to check if the arr can be// converted to target by replacing// any element in arr by the sum of arrfunction isPossible(target){ // Store the maximum element var max = 0; // Store the index of // the maximum element var index = 0; // Traverse the array target for (i = 0; i < target.length; i++) { // If current element is // greater than max if (max < target[i]) { max = target[i]; index = i; } } // If max element is 1 if (max == 1) return true; // Traverse the array, target for (i = 0; i < target.length; i++) { // If current index is not equal to // maximum element index if (i != index) { // Update max max -= target[i]; // If max is less than // or equal to 0, if (max <= 0) return false; } } // Update the maximum element target[index] = max; // Recursively call the function return isPossible(target);}// Driver Codevar target = [ 9, 3, 5 ];res = isPossible(target);if (res) { document.write("YES");}else { document.write("NO");}// This code is contributed by 29AjayKumar </script> |
Output
YES
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: This type of problem are purely intuition based and can be solved easily just by doing some observations …
Notice that we are getting a pattern in the target array if we make it sorted.Take a look at examples
Examples:
1: input[] = { 1, 1, 1 }, target[] = { 9, 3, 5 }
sorted(target[])={3,5,9} and the output will be for this array is YES
2: input[] = { 1, 1, 1,1 }, target[] = { 4,,25,7,13}
sorted(target[])={4,7,13,25} and the output will be for this array is YES
3: input[]={1,1,1,1,1} ,target[]={33,65,5,9,17}
sorted(target[])={5,9,17,33,65} and the output will be for this array is YES
From the above mentioned examples, it is clear that for size(target[])=n, sorted(target[]) should start from n and successive elements of the target[] array will be as : target[i]=2*target[i-1]-1 and so on.
if sorted(target) array follows this pattern, then result will be YES ,else NO….
Approach Steps:
- Sort the target[] array first.
- Store length of target[] array into n.
- if sorted(target[]) does not start from n, then return “NO”.
- Traverse sorted(target[]) from index 1 to last.
- If target[i] != 2* target[ i-1]-1 at any step,then return “NO”, else after completing traversal return “YES”………….improved by Rajat Kumar.
Below is the implementation of the above approach:
Java
// Java program to implement the above approach// Function to check if the arr[] can be// converted to target[] by replacing// any element in arr[] by the sum of arr[]import java.io.*;import java.util.*;class GFG { // Function to check if the arr[] can be // converted to target[] by replacing // any element in arr[] by the sum of arr[] public static boolean isPossible(int[] target) { // sort the target array Arrays.sort(target); // store length of target into n int n = target.length; // check if target[0] is equal to n or not? if (target[0] != n) { return false; } // Traverse the array further for checking // whether array follows the pattern or not ? for (int i = 1; i < n; i++) { if (target[i] != 2 * target[i - 1] - 1) { // if an element does not follow the pattern // return False return false; } } // After checking all the elements at the last, // return True return true; } public static void main(String[] args) { int[] target = { 9, 3, 5 }; boolean res = isPossible(target); if (res) { System.out.println("YES"); } else { System.out.println("NO"); } }}// This code is contributed by lokesh. |
Python3
# Python program to implement the above approach# Function to check if the arr[] can be# converted to target[] by replacing# any element in arr[] by the sum of arr[]def isPossible(target): # sort the target array # this step is dominating step # in time complexity having #time complexity O(n logn). target.sort() # store length of target into n n = len(target) # check if target[0] is equal to n or not? if target[0] != n: return False # Traverse the array further for checking # whether array follows the pattern or not ? for i in range(1, n): if target[i] != 2*target[i-1]-1: # if an element does not follow the pattern # return False return False # After checking all the elements at the last, return True return True# Driver Codetarget = [9, 3, 5]res = isPossible(target)if (res): print("YES")else: print("NO")""" Code is written by Rajat kumar(rajatkumargla19)... """ |
C#
// C# code for the above approachusing System;public class GFG { // Function to check if the arr[] can be // converted to target[] by replacing // any element in arr[] by the sum of arr[] public static bool IsPossible(int[] target) { // sort the target array Array.Sort(target); // store length of target into n int n = target.Length; // check if target[0] is equal to n or not? if (target[0] != n) { return false; } // Traverse the array further for checking // whether array follows the pattern or not ? for (int i = 1; i < n; i++) { if (target[i] != 2 * target[i - 1] - 1) { // if an element does not follow the pattern // return False return false; } } // After checking all the elements at the last, // return True return true; } static public void Main() { // Code int[] target = { 9, 3, 5 }; bool res = IsPossible(target); if (res) { Console.WriteLine("YES"); } else { Console.WriteLine("NO"); } }}// This code is contributed by lokeshmvs21. |
Javascript
// JS program to implement the above approach// Function to check if the arr[] can be// converted to target[] by replacing// any element in arr[] by the sum of arr[]function isPossible(target){ // sort the target array // this step is dominating step // in time complexity having //time complexity O(n logn). target.sort(function(a, b) { return a - b; }) // store length of target into n let n = target.length // check if target[0] is equal to n or not? if (target[0] != n) return false // Traverse the array further for checking // whether array follows the pattern or not ? for (var i = 1; i < n; i++) if (target[i] != 2*target[i-1]-1) // if an element does not follow the pattern // return false return false // After checking all the elements at the last, return True return true}// Driver Codelet target = [9, 3, 5]let res = isPossible(target)if (res) console.log("YES")else console.log("NO")// This code is contributed by phasing17. |
C++14
#include <algorithm>#include <iostream>#include <vector>// Function to check if the arr[] can be// converted to target[] by replacing// any element in arr[] by the sum of arr[]bool isPossible(std::vector<int> target) { // sort the target array std::sort(target.begin(), target.end()); // store length of target into n int n = target.size(); // check if target[0] is equal to n or not? if (target[0] != n) { return false; } // Traverse the array further for checking // whether array follows the pattern or not ? for (int i = 1; i < n; i++) { if (target[i] != 2 * target[i - 1] - 1) { // if an element does not follow the pattern // return False return false; } } // After checking all the elements at the last, // return True return true;}int main() { std::vector<int> target = {9, 3, 5}; bool res = isPossible(target); if (res) { std::cout << "YES" << std::endl; } else { std::cout << "NO" << std::endl; } return 0;} |
Output
YES
Time Complexity: O(nlogn) as sorting takes O(nlogn)
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!
