Array entrada[] 1 destino[] N entrada[] destino[] entrada[i]
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 ingenuo: el enfoque ingenuo y el enfoque codicioso ya se mencionan en el Conjunto 1 de este artículo.
Enfoque eficiente: la idea de resolver el problema de manera eficiente se basa en la siguiente intuición:
- En lugar de intentar verificar si se puede alcanzar la array target[] , trabaje hacia atrás e intente generar la array de 1 a partir de target[].
- Mientras se trabaja hacia atrás, el elemento máximo de la array será la suma de los elementos después del último turno. Para realizar un seguimiento del elemento máximo, use un montón máximo .
- Después de cada turno, elimine el elemento máximo del montón y determine el valor máximo anterior del elemento. Para hacer esto, encuentre la suma de todos los elementos de la array.
Siga los pasos para resolver el problema:
- Cree las variables sum y lastSum para almacenar la suma de todos los elementos, la suma de la array en el paso anterior.
- Para determinar el elemento anterior, encuentra la diferencia de “sum” y “lastSum” de “lastSum”, es decir (lastSum – (sum – lastSum)).
- Luego, vuelva a colocar este valor en el montón y actualice la suma .
- Continúe con esto hasta que la suma sea igual a uno o hasta que lastSum sea igual a uno.
- En caso de que lastSum sea menor que sum o sum sea igual a cero o la diferencia de lastSum y sum sea cero, devuelve falso.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
// Function to find if target[] can be reached
bool createTarget(vector<int>& target)
{
// Initialise size of target array
int n = target.size();
// Initialise variable to store
// sum of values
int sum = 0;
// Initialise variable to store
// last sum
int lastSum;
// Initialise a max-heap to keep track
// of the maximum element
priority_queue<int> maxHeap(target.begin(),
target.end());
// Start traversing to find the sum
for (int i = 0; i < n; i++) {
sum = sum + target[i];
}
// While heap has element traverse
while (true) {
// Update last sum with
// maximum value of heap
lastSum = maxHeap.top();
// Pop the maximum element
// of the heap
maxHeap.pop();
// Update sum of values
sum = sum - lastSum;
// If either sum or last sum is
// equal to 1, then
// target array possible
if (lastSum == 1 || sum == 1) {
// Return true
return true;
}
// If last sum becomes less than
// sum or if sum becomes equal
// to 0 or if difference of last
// sum and sum becomes 0
if (lastSum < sum || sum == 0
|| lastSum - sum == 0) {
// Return false
return false;
}
// Update last sum
lastSum = lastSum - sum;
// Update sum
sum = sum + lastSum;
// Push last sum into the queue
maxHeap.push(lastSum);
}
}
// Driver code
int main()
{
int N = 2;
vector<int> target = { 2, 3 };
bool ans = createTarget(target);
if (ans)
cout << "YES";
else
cout << "NO";
return 0;
}
Java
// Java code for the above approach:
import java.util.*;
// Function to find if target[] can be reached
class GFG {
static boolean createTarget(int[] target)
{
// Initialise size of target array
int n = target.length;
// Initialise variable to store
// sum of values
int sum = 0;
// Initialise variable to store
// last sum
int lastSum = 0;
// Initialise a max-heap to keep track
// of the maximum element
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>();
for (int i = 0; i < target.length; i++)
// we are using negative values as we want to remove the maximum element
// from the priority queue, however, by default the minimum element i removed using poll()
maxHeap.add(-1 * target[i]);
// Start traversing to find the sum
for (int i = 0; i < n; i++)
sum += target[i];
// While heap has element traverse
while (true)
{
// Update last sum with
// maximum value of heap and also
//remove the maximum value from heap
lastSum = -1 * maxHeap.poll();
// Update sum of values
sum -= lastSum;
// If either sum or last sum is
// equal to 1, then
// target array possible
if (lastSum == 1 || sum == 1)
{
return true;
}
// If last sum becomes less than
// sum or if sum becomes equal
// to 0 or if difference of last
// sum and sum becomes 0
if (lastSum <= sum || sum == 0 )
{
return false;
}
// update lastsum and sum
lastSum = lastSum - sum;
sum += lastSum;
// Push last sum into the queue
maxHeap.add(-1 * lastSum);
}
}
// Driver code
public static void main(String[] args) {
int N = 2;
int[] target = {2, 3};
boolean ans = createTarget(target);
if (ans)
System.out.println("YES");
else
System.out.println("NO");
}
}
// This code is contributed by phasing17
Python3
# python3 code for the above approach:
from queue import PriorityQueue
# Function to find if target[] can be reached
def createTarget(target):
# Initialise size of target array
n = len(target)
# Initialise variable to store
# sum of values
sum = 0
# Initialise variable to store
# last sum
lastSum = 0
# Initialise a max-heap to keep track
# of the maximum element
maxHeap = PriorityQueue()
for itm in target:
maxHeap.put(-itm)
# Start traversing to find the sum
for i in range(0, n):
sum = sum + target[i]
# While heap has element traverse
while True:
# Update last sum with
# maximum value of heap
lastSum = -maxHeap.get()
# Pop the maximum element
# of the heap
# Update sum of values
sum = sum - lastSum
# If either sum or last sum is
# equal to 1, then
# target array possible
if (lastSum == 1 or sum == 1):
# Return true
return True
# If last sum becomes less than
# sum or if sum becomes equal
# to 0 or if difference of last
# sum and sum becomes 0
if (lastSum < sum or sum == 0
or lastSum - sum == 0):
# Return false
return False
# Update last sum
lastSum = lastSum - sum
# Update sum
sum = sum + lastSum
# Push last sum into the queue
maxHeap.put(-lastSum)
# Driver code
if __name__ == "__main__":
N = 2
target = [2, 3]
ans = createTarget(target)
if (ans):
print("YES")
else:
print("NO")
# This code is contributed by rakeshsahni
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG
{
static bool createTarget(int[] target)
{
// Initialise size of target array
int n = target.Length;
// Initialise variable to store
// sum of values
int sum = 0;
// Initialise variable to store
// last sum
int lastSum = 0;
// Initialise a max-heap to keep track
// of the maximum element
List<int> maxHeap = new List<int>();
for (int i = 0; i < target.Length; i++)
// we are using negative values as we want to remove the maximum element
// from the priority queue, however, by default the minimum element i removed using poll()
maxHeap.Add(-1 * target[i]);
// Start traversing to find the sum
for (int i = 0; i < n; i++)
sum += target[i];
// While heap has element traverse
while (true)
{
// Update last sum with
// maximum value of heap and also
//remove the maximum value from heap
// Update last sum with
// maximum value of heap
lastSum = maxHeap[0];
// Pop the maximum element
// of the heap
maxHeap.RemoveAt(0);
// Update sum of values
sum -= lastSum;
// If either sum or last sum is
// equal to 1, then
// target array possible
if (lastSum == 1 || sum == 1)
{
return true;
}
// If last sum becomes less than
// sum or if sum becomes equal
// to 0 or if difference of last
// sum and sum becomes 0
if (lastSum <= sum || sum == 0 )
{
return false;
}
// update lastsum and sum
lastSum = lastSum - sum;
sum += lastSum;
// Push last sum into the queue
maxHeap.Add(-1 * lastSum);
}
}
// Driver Code
public static void Main()
{
int N = 2;
int[] target = {2, 3};
bool ans = createTarget(target);
if (ans == false)
Console.Write("YES");
else
Console.Write("NO");
}
}
// This code is contributed by sanjoy_62.
Javascript
// JavaScript program to implement
// the above approach
function createTarget(target)
{
// Initialise size of target array
var n = target.length;
// Initialise variable to store
// sum of values
var sum = 0;
// Initialise variable to store
// last sum
var lastSum = 0;
// Initialise a max-heap to keep track
// of the maximum element
maxHeap = [];
for (var i = 0; i < target.length; i++)
// we are using negative values as we want to remove
// the maximum element from the priority queue,
// however, by default the minimum element i removed
// using poll()
maxHeap.push(-1 * target[i]);
// Start traversing to find the sum
for (var i = 0; i < n; i++)
sum += target[i];
// While heap has element traverse
while (true) {
// Update last sum with
// maximum value of heap and also
// remove the maximum value from heap
// Update last sum with
// maximum value of heap
lastSum = maxHeap[0];
// Pop the maximum element
// of the heap
maxHeap.splice(0, 1);
// Update sum of values
sum -= lastSum;
// If either sum or last sum is
// equal to 1, then
// target array possible
if (lastSum == 1 || sum == 1) {
return true;
}
// If last sum becomes less than
// sum or if sum becomes equal
// to 0 or if difference of last
// sum and sum becomes 0
if (lastSum <= sum || sum == 0) {
return false;
}
// update lastsum and sum
lastSum = lastSum - sum;
sum += lastSum;
// Push last sum into the queue
maxHeap.pushh(-1 * lastSum);
}
}
// Driver Code
var N = 2;
var target = [ 2, 3 ];
var ans = createTarget(target);
if (ans == false)
console.log("YES");
else
console.log("NO");
// This code is contributed by phasing17
Producción
true
Complejidad temporal: O(N * log(N) + (K / N * log(N))), donde K es el elemento máximo del arreglo.
Espacio Auxiliar: O(N)