Dada una entrada de array [] que consta solo de 1 s inicialmente y una array objetivo [] de tamaño N , la tarea es verificar si la entrada de array [] se puede convertir en objetivo [] reemplazando entrada [i] con la suma de elementos de array en cada paso. Si se encuentra que es cierto, escriba «SÍ» . De lo contrario, escriba «NO» .
Ejemplos:
Entrada: entrada[] = { 1, 1, 1 }, objetivo[] = { 9, 3, 5 }
Salida: SÍ
Explicación:
Reemplazar entrada[1] con (entrada[0] + entrada[1] + entrada[2 ]) modifica input[] a { 1, 3, 1 }
Reemplazando input[2] con (input[0] + input[1] + input[2]) modifica input[] a { 1, 3, 5 }
Reemplazando input [0] con (input[0] + input[1] + input[2]) modifica input[] a { 9, 3, 5 }
Dado que la array input[] es igual a la array target[], la salida requerida es «SÍ».Entrada: entrada[] = { 1, 1, 1, 1 }, objetivo[] = { 1, 1, 1, 2 }
Salida: NO
Enfoque: El problema se puede resolver usando la técnica Greedy . La idea es disminuir siempre el elemento más grande de la array target[] por la suma de los elementos restantes de la array y verificar si es el elemento más grande de target[] . Si se encuentra que es cierto, escriba «SÍ» . De lo contrario, escriba «NO» . Las siguientes son las observaciones:
Si target[] = { 9, 3, 5 } e input[] = { 1, 1, 1 }
Decrementar target[0] por (target[1] + target[2]) modifica target[] a { 1, 3 , 5 }
Decrementar objetivo[2] en (objetivo[0] + objetivo[1]) modifica objetivo[] a { 1, 3, 1 }
Decrementar objetivo[1] en (objetivo[0] + objetivo[2]) modifica target[] a { 1, 1, 1 }
Dado que input[] array y target[] son iguales, la salida requerida es SÍ.
- Si el elemento más grande en la array target[] es menor que 1 , imprima «NO» .
- Si el elemento más grande en la array objetivo[] es igual a 1 , entonces imprima «SÍ» .
- De lo contrario, disminuya el elemento más grande de la array target[] por la suma de los elementos restantes presentes en la array target[] mientras que el elemento más grande de la array es mayor que 1 .
A continuación se muestra la implementación del enfoque anterior:
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 Code
int 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 approach
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)
{
// 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 Code
target = [ 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 approach
using 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 Code
static 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 arr
function 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 Code
var target = [ 9, 3, 5 ];
res = isPossible(target);
if (res) {
document.write("YES");
}
else {
document.write("NO");
}
// This code is contributed by 29AjayKumar
</script>
YES
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rohit2sahu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA