Given a array of n integers, we need to check whether for every pair of numbers a[i] & a[j] there exists a a[k] such that a[k] = a[i]*a[j] where k can be equal to i or j too.
Examples :
Input : arr[] = {0. 1}
Output : Yes
Here a[0]*a[1] is equal to a[0]
Input : arr[] = {5, 6}
Output : No
An array will satisfy the problem conditions if the array follows all the below mentioned conditions :
- Condition 1 : The array must have number of elements other than 1, 0, -1 less than or equal to 1 because if it has more than 1 such elements there will be no element present in the array whose product will be equal to the largest of those two (or more) elements. Suppose that number of such elements be 2 and their values are 5, 6 so there is no element equal to 5*6 = 30 in the array.
- Condition 2 : If the array has an other number say x (other than 0, 1 and -1) and -1 is also present, then also answer is false. Because presence of -1 makes it required that both x and -x should be present, but this violates condition 1.
- Condition 3 : if there are more than one “-1” and no one in the array then also answer will be no because the product of two “-1” is equal to 1.
Below is the implementation of above conditions.
C++
// C++ program to find if // product of every pair// is present in array.#include<bits/stdc++.h>using namespace std;// Returns true if product // of every pair in arr[]// is present in arr[]bool checkArray(int arr[] , int n){ // variable to store number // of zeroes, ones, minus // one and other numbers. int zero = 0, one = 0, minusone = 0, other=0; for (int i = 0; i < n; i++) { // incrementing the // variable values if (arr[i] == 0) zero++; else if (arr[i] == 1) one++; else if (arr[i] == -1) minusone++; else other++; } // checking the conditions if (other > 1) return false; else if (other != 0 && minusone != 0) return false; else if (minusone > 1 && one == 0) return false; return true;}// Driver Codeint main(){ int arr[] = {0, 1, 1, 10}; int n = sizeof(arr) / sizeof(arr[0]); if (checkArray(arr, n)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java program to find // if product of every pair// is present in array.class GFG{ // Returns true if product // of every pair in arr[] // is present in arr[] static boolean checkArray(int arr[] , int n) { // variable to store number // of zeroes, ones, minus // one and other numbers. int zero = 0, one = 0, minusone = 0, other=0; for (int i = 0; i < n; i++) { // incrementing the // variable values if (arr[i] == 0) zero++; else if (arr[i] == 1) one++; else if (arr[i] == -1) minusone++; else other++; } // checking the conditions if (other > 1) return false; else if (other != 0 && minusone != 0) return false; else if (minusone > 1 && one == 0) return false; return true; } // Driver Code public static void main (String[] args) { int arr[] = {0, 1, 1, 10}; int n = arr.length; if (checkArray(arr, n)) System.out.println("Yes"); else System.out.println("No"); }}// This code is contributed by Harsh Agarwal |
Python3
# Python3 program to find# if product of every pair# is present in array.# Returns True if product# of every pair in arr[] is # present in arr[]def checkArray(arr, n): # variable to store number # of zeroes, ones, minus # one and other numbers. zero = 0; one = 0; minusone = 0; other = 0 for i in range(0, n): # incrementing the # variable values if (arr[i] == 0): zero += 1 elif (arr[i] == 1): one += 1 elif (arr[i] == -1): minusone += 1 else: other += 1 # checking the conditions if (other > 1): return false elif (other != 0 and minusone != 0): return false elif (minusone > 1 and one == 0): return false return True# Driver Codearr = [0, 1, 1, 10]n = len(arr)if (checkArray(arr, n)): print("Yes")else: print("No") # This code is contributed# by Smitha Dinesh Semwal. |
C#
// C# program to find if // product of every pair // is present in array.using System;class GFG{ // Returns true if product // of every pair in arr[] // is present in arr[] static Boolean checkArray(int []arr , int n) { // variable to store number // of zeroes, ones, minus // one and other numbers. int zero = 0, one = 0, minusone = 0, other=0; for (int i = 0; i < n; i++) { // incrementing the // variable values if (arr[i] == 0) zero++; else if (arr[i] == 1) one++; else if (arr[i] == -1) minusone++; else other++; } // checking the conditions if (other > 1) return false; else if (other != 0 && minusone != 0) return false; else if (minusone > 1 && one == 0) return false; return true; } // Driver Code public static void Main (String[] args) { int []arr = {0, 1, 1, 10}; int n = arr.Length; if (checkArray(arr, n)) Console.Write("Yes"); else Console.Write("No"); }}// This code is contributed by parashar.... |
PHP
<?php// PHP program to find if // product of every pair// is present in array.// Returns true if product // of every pair in arr[]// is present in arr[]function checkArray($arr , $n){ // variable to store number // of zeroes, ones, minus // one and other numbers. $zero = 0; $one = 0; $minusone = 0; $other=0; for ($i = 0; $i < $n; $i++) { // incrementing the // variable values if ($arr[$i] == 0) $zero++; else if ($arr[$i] == 1) $one++; else if ($arr[$i] == -1) $minusone++; else $other++; } // checking the conditions if ($other > 1) return false; else if ($other != 0 && $minusone != 0) return false; else if ($minusone > 1 && $one == 0) return false; return true;}// Driver Code{ $arr = array(0, 1, 1, 10); $n = sizeof($arr) / sizeof($arr[0]); if (checkArray($arr, $n)) echo "Yes"; else echo "No"; return 0;}//This code is contributed// by nitin mittal.?> |
Javascript
<script>//javascript program to find if// product of every pair// is present in array.// Returns true if product// of every pair in arr[]// is present in arr[]function checkArray(arr,n){ // variable to store number // of zeroes, ones, minus // one and other numbers. let zero = 0, one = 0, minusone = 0, other=0; for (let i = 0; i < n; i++) { // incrementing the // variable values if (arr[i] == 0) zero++; else if (arr[i] == 1) one++; else if (arr[i] == -1) minusone++; else other++; } // checking the conditions if (other > 1) return false; else if (other != 0 && minusone != 0) return false; else if (minusone > 1 && one == 0) return false; return true;} let arr = [0, 1, 1, 10]; let n = arr.length; if (checkArray(arr, n)) document.write("Yes"); else document.write("No");// This code is contributed by vaibhavrabadiya117.</script> |
Output
Yes
Time Complexity: O(n)
Auxiliary Space: O(1)
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
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!
