Given an array of N elements, the task is to check if the array has an element which is equal to the product of all the remaining elements.
Examples:
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
Method-1:
- First, take the product of all the element of the array.
- Now traverse the whole array again.
- For any element a[i] check if it is equal to the product of all elements divided by that element.
- Print Yes if at least one such element is found.
Below is the implementation of the above approach:
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 elementsbool 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 approachimport java.io.*;class GFG {// Function to Check if the array// has an element which is equal to// product of all the remaining elementsstatic 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 elementsdef 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 codeif __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 approachclass GFG{// Function to Check if the array// has an element which is equal to// product of all the remaining elementsstatic 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 Codepublic 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 elementsfunction 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 elementsfunction 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> |
Output
YES
Complexity Analysis:
- Time Complexity: O(n)
- Auxiliary Space: O(1)
Method-2:
The approach is to find the product of all the elements of the array and check if it is a perfect square or not. If it is a perfect square then check if the square root of the product exists in the array or not. If exists then print Yes else print No.
According to the problem statement, a * b = N
where b is the product of all the remaining elements of the array except a i.e arr[i]
And it is also mentioned that find the index such that a = b.
So, it simply means that a*a = N i.e. N is a perfect square. and a is its square root.
Below is the implementation of the above approach:
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 elementsbool 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 codeint 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 approachclass 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 elementsdef 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 codeif __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 elementsfunction 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> |
Output
YES
Complexity Analysis:
- Time Complexity: O(n)
- Auxiliary Space: O(n)
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!
… [Trackback]
[…] Here you can find 48581 additional Information on that Topic: geeksforgeeks.org/check-if-the-array-has-an-element-which-is-equal-to-product-of-remaining-elements/ […]