Count of elements which is product of a pair or an element square | C ++ Program to implement the above approach ; Stores all factors a number ; Function to calculate and store in a vector ; Function to return the count of array elements which are a product of two array elements ; Copy elements into a a duplicate array ; Sort the duplicate array ; Store the count of elements ; If the factors are not calculated already ; Traverse its factors ; If a pair of factors is found ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > v [ 100000 ] ; void div ( int n ) { for ( int i = 2 ; i <= sqrt ( n ) ; i ++ ) { if ( n % i == 0 ) { v [ n ] . push_back ( i ) ; } } } int prodof2elements ( int arr [ ] , int n ) { int arr2 [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { arr2 [ i ] = arr [ i ] ; } sort ( arr2 , arr2 + n ) ; int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( v [ arr [ i ] ] . size ( ) == 0 ) div ( arr [ i ] ) ; for ( auto j : v [ arr [ i ] ] ) { if ( binary_search ( arr2 , arr2 + n , j ) and binary_search ( arr2 , arr2 + n , arr [ i ] / j ) ) { ans ++ ; break ; } } } return ans ; } int main ( ) { int arr [ ] = { 2 , 1 , 8 , 4 , 32 , 18 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << prodof2elements ( arr , N ) ; return 0 ; }