Dada una array de N elementos, la tarea es verificar si la array tiene un elemento que sea igual al producto de todos los elementos restantes.
Ejemplos:
Input: arr[] = {1, 2, 12, 3, 2}
Output: YES
12 is the product of all the remaining elements
i.e. 1 * 2 * 3 * 2 = 12
Input: arr[] = {1, 2, 3}
Output: NO
Método 1:
- Primero, toma el producto de todos los elementos de la array.
- Ahora recorra toda la array nuevamente.
- Para cualquier elemento a[i] comprueba si es igual al producto de todos los elementos dividido por ese elemento.
- Escriba Sí si se encuentra al menos uno de esos elementos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to Check if the array
// has an element which is equal to
// product of all the remaining elements
bool CheckArray(int arr[], int n)
{
int prod = 1;
// Calculate the product of all the elements
for (int i = 0; i < n; ++i)
prod *= arr[i];
// Return true if any such element is found
for (int i = 0; i < n; ++i)
if (arr[i] == prod / arr[i])
return true;
// If no element is found
return false;
}
int main()
{
int arr[] = { 1, 2, 12, 3, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
if (CheckArray(arr, n))
cout << "YES";
else
cout << "NO";
return 0;
}
Java
// Java implementation of the above approach
import java.io.*;
class GFG {
// Function to Check if the array
// has an element which is equal to
// product of all the remaining elements
static boolean CheckArray(int arr[], int n)
{
int prod = 1;
// Calculate the product of all the elements
for (int i = 0; i < n; ++i)
prod *= arr[i];
// Return true if any such element is found
for (int i = 0; i < n; ++i)
if (arr[i] == prod / arr[i])
return true;
// If no element is found
return false;
}
public static void main (String[] args) {
int arr[] = { 1, 2, 12, 3, 2 };
int n =arr.length;
if (CheckArray(arr, n))
System.out.println("YES");
else
System.out.println("NO");
}
}
// This code is contributed by shs..
Python3
# Python 3 implementation of the above approach
# Function to Check if the array
# has an element which is equal to
# product of all the remaining elements
def CheckArray(arr, n):
prod = 1
# Calculate the product of all
# the elements
for i in range(0, n, 1):
prod *= arr[i]
# Return true if any such element
# is found
for i in range(0, n, 1):
if (arr[i] == prod / arr[i]):
return True
# If no element is found
return False
# Driver code
if __name__ == '__main__':
arr = [1, 2, 12, 3, 2]
n = len(arr)
if (CheckArray(arr, n)):
print("YES")
else:
print("NO")
# This code is contributed by
# Surendra_Gangwar
C#
// C# implementation of the above approach
class GFG
{
// Function to Check if the array
// has an element which is equal to
// product of all the remaining elements
static bool CheckArray(int[] arr, int n)
{
int prod = 1;
// Calculate the product of
// all the elements
for (int i = 0; i < n; ++i)
prod *= arr[i];
// Return true if any such
// element is found
for (int i = 0; i < n; ++i)
if (arr[i] == prod / arr[i])
return true;
// If no element is found
return false;
}
// Driver Code
public static void Main ()
{
int[] arr = new int[] { 1, 2, 12, 3, 2 };
int n = arr.Length;
if (CheckArray(arr, n))
System.Console.WriteLine("YES");
else
System.Console.WriteLine("NO");
}
}
// This code is contributed by mits
PHP
<?php
// PHP implementation of the above approach
// Function to Check if the array
// has an element which is equal to
// product of all the remaining elements
function CheckArray($arr, $n)
{
$prod = 1;
// Calculate the product of
// all the elements
for ($i = 0; $i < $n; ++$i)
$prod *= $arr[$i];
// Return true if any such element
// is found
for ($i = 0; $i < $n; ++$i)
if ($arr[$i] == $prod / $arr[$i])
return true;
// If no element is found
return false;
}
// Driver Code
$arr = array(1, 2, 12, 3, 2);
$n = sizeof($arr);
if (CheckArray($arr, $n))
echo "YES";
else
echo "NO";
// This code is contributed
// by Akanksha Rai
Javascript
<script>
// Java script implementation of the above approach
// Function to Check if the array
// has an element which is equal to
// product of all the remaining elements
function CheckArray(arr,n)
{
let prod = 1;
// Calculate the product of all the elements
for (let i = 0; i < n; ++i)
prod *= arr[i];
// Return true if any such element is found
for (let i = 0; i < n; ++i)
if (arr[i] == prod / arr[i])
return true;
// If no element is found
return false;
}
let arr = [ 1, 2, 12, 3, 2 ];
let n =arr.length;
if (CheckArray(arr, n))
document.write("YES");
else
document.write("NO");
// This code is contributed by sravan kumar Gottumukkala
</script>
Producción:
YES
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Método 2: el enfoque es encontrar el producto de todos los elementos de la array y verificar si es un cuadrado perfecto o no. Si es un cuadrado perfecto, compruebe si la raíz cuadrada del producto existe en la array o no. Si existe, imprima Sí; de lo contrario, imprima No.
De acuerdo con el enunciado del problema, a * b = N
donde b es el producto de todos los elementos restantes del arreglo excepto a ie arr[i]
Y también se menciona que encuentre el índice tal que a = b .
Entonces, simplemente significa que a*a = N, es decir, N es un cuadrado perfecto. y a es su raíz cuadrada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to Check if the array
// has an element which is equal to
// product of all the remaining elements
bool CheckArray(int arr[], int n)
{
int prod = 1;
// Storing frequency in map
unordered_set<int> freq;
// Calculate the product of all the elements
for (int i = 0; i < n; ++i) {
freq.insert(arr[i]);
prod *= arr[i];
}
int root = sqrt(prod);
// If the prod is a perfect square
if (root * root == prod)
// then check if its square root
// exist in the array or not
if (freq.find(root) != freq.end())
return true;
return false;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 12, 3, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
if (CheckArray(arr, n))
cout << "YES";
else
cout << "NO";
return 0;
}
Java
import java.util.ArrayList;
// Java implementation of the above approach
class GFG {
// Function to Check if the array
// has an element which is equal to
// product of all the remaining elements
static boolean CheckArray(int arr[], int n) {
int prod = 1;
// Storing frequency in map
ArrayList<Integer> freq = new ArrayList<>();
// Calculate the product of all the elements
for (int i = 0; i < n; ++i) {
freq.add(arr[i]);
prod *= arr[i];
}
int root = (int) Math.sqrt(prod);
// If the prod is a perfect square
if (root * root == prod) // then check if its square root
// exist in the array or not
{
if (freq.contains(root) & freq.lastIndexOf(root) != (freq.size())) {
return true;
}
}
return false;
}
// Driver code
public static void main(String[] args) {
int arr[] = {1, 2, 12, 3, 2};
int n = arr.length;
if (CheckArray(arr, n)) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
//This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the above approach
import math
# Function to Check if the array
# has an element which is equal to
# product of all the remaining elements
def CheckArray( arr, n):
prod = 1
# Storing frequency in map
freq = []
# Calculate the product of all the elements
for i in range(n) :
freq.append(arr[i])
prod *= arr[i]
root = math.sqrt(prod)
# If the prod is a perfect square
if (root * root == prod):
# then check if its square root
# exist in the array or not
if root in freq:
return True
return False
# Driver code
if __name__ == "__main__":
arr = [1, 2, 12, 3, 2 ]
n = len(arr)
if (CheckArray(arr, n)):
print ("YES")
else:
print ("NO")
C#
// C# implementation of above approach
using System;
using System.Collections;
class GFG
{
// Function to Check if the array
// has an element which is equal to
// product of all the remaining elements
static bool CheckArray(int []arr, int n)
{
int prod = 1;
// Storing frequency in map
ArrayList freq = new ArrayList();
// Calculate the product of all the elements
for (int i = 0; i < n; ++i)
{
freq.Add(arr[i]);
prod *= arr[i];
}
int root = (int) Math.Sqrt(prod);
// If the prod is a perfect square
if (root * root == prod) // then check if its square root
// exist in the array or not
{
if (freq.Contains(root) & freq.LastIndexOf(root) != (freq.Count))
{
return true;
}
}
return false;
}
// Driver code
public static void Main()
{
int []arr = {1, 2, 12, 3, 2};
int n = arr.Length;
if (CheckArray(arr, n))
{
Console.WriteLine("YES");
}
else
{
Console.WriteLine("NO");
}
}
}
/* This code contributed by PrinciRaj1992 */
PHP
<?php
// PHP implementation of the above approach
// Function to Check if the array
// has an element which is equal to
// product of all the remaining elements
function CheckArray($arr, $n)
{
$prod = 1;
// Storing frequency in map
$freq = array();
// Calculate the product of all the elements
for ($i = 0; $i < $n; ++$i)
{
array_push($freq, $arr[$i]);
$prod *= $arr[$i];
}
$freq = array_unique($freq);
$root = (int)(sqrt($prod));
// If the prod is a perfect square
if ($root * $root == $prod)
// then check if its square root
// exist in the array or not
if (in_array($root, $freq))
return true;
return false;
}
// Driver code
$arr = array( 1, 2, 12, 3, 2 );
$n = count($arr);
if (CheckArray($arr, $n))
echo "YES";
else
echo "NO";
// This code is contributed by mits
?>
Javascript
<script>
// JavaScript implementation of
// the above approach
// Function to Check if the array
// has an element which is equal to
// product of all the remaining elements
function CheckArray(arr,n)
{
let prod = 1;
// Storing frequency in map
let freq = [];
// Calculate the product of all the elements
for (let i = 0; i < n; ++i) {
freq.push(arr[i]);
prod *= arr[i];
}
let root = Math.floor(Math.sqrt(prod));
// If the prod is a perfect square
// then check if its square root
if (root * root == prod)
// exist in the array or not
{
if (freq.includes(root) &
freq.lastIndexOf(root) != (freq.length))
{
return true;
}
}
return false;
}
// Driver code
let arr=[1, 2, 12, 3, 2];
let n = arr.length;
if (CheckArray(arr, n)) {
document.write("YES");
} else {
document.write("NO");
}
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
YES
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por imdhruvgupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA