Find all pairs such that (X, Y) such that X^2 = Y and X < Y
Given an array arr[] of positive integers, the task is to find the count of all the pairs (X, Y) in the array such that X2=Y and Y>X.
Examples:
Input: arr[] = {2, 4, 8, 16, 9, 81, 3}
Output: 4
Explanation: There are 4 such pairs (2, 4), (4, 16), (9, 81), (3, 9) such that X2 = YInput: arr[] = {2, 4, 16, 32, 1, 1, 1}
Output: 2
Explanation: There are 4 such pairs (2, 4), (4, 16) such that X2=Y
Approach: This can be solved with the following idea:
For X2 = Y, we will use an efficient hash map that will store key-value pairs.
Steps involved in the implementation of the code:
- Initialize countPair variable with 0.
- Traverse the Array from left to right and increment the count of each number using the hash map.
- Again traverse the array from left to right and let the array element be X. Add the count of occurrences of the number X2 to the countPair variable.
- Display countPair.
- There is an edge case where X = Y and X2 = Y for X = 1 and so neglect it since X < Y.
Below is the implementation of the code:
C++
// C++ Implementation of the code #include <bits/stdc++.h> using namespace std; // Function to find count of pairs such // that (X x X= Y) int countPairs(vector< int >& arr, int n) { int countPair = 0, X, Y; unordered_map< int , int > countNum; // Store the element in the map for ( int i = 0; i < n; i++) { countNum[arr[i]]++; } // Check for element presence for ( int i = 0; i < n; i++) { if (arr[i] != 1) { X = arr[i]; Y = X * X; countPair += countNum[Y]; } } return countPair; } // Driver code int main() { vector< int > arr = { 16, 4, 4, 4, 2, 2, 2 }; int n = arr.size(); // Function call cout << countPairs(arr, n) << endl; return 0; } |
Java
// Java implementation of the code import java.util.*; public class CountPairs { // Function to find count of pairs such that (X x X = Y) static int countPairs(List<Integer> arr, int n) { int countPair = 0 , X, Y; Map<Integer, Integer> countNum = new HashMap<>(); // Store the element in the map for ( int i = 0 ; i < n; i++) { countNum.put(arr.get(i), countNum.getOrDefault(arr.get(i), 0 ) + 1 ); } // Check for element presence for ( int i = 0 ; i < n; i++) { if (arr.get(i) != 1 ) { X = arr.get(i); Y = X * X; countPair += countNum.getOrDefault(Y, 0 ); } } return countPair; } // Driver code public static void main(String[] args) { List<Integer> arr = Arrays.asList( 16 , 4 , 4 , 4 , 2 , 2 , 2 ); int n = arr.size(); // Function call System.out.println(countPairs(arr, n)); } } |
Python3
# code # Function to find count of pairs such that (X * X = Y) def countPairs(arr, n): countPair = 0 countNum = {} # Store the element in the dictionary for i in range (n): countNum[arr[i]] = countNum.get(arr[i], 0 ) + 1 # Check for element presence for i in range (n): if arr[i] ! = 1 : X = arr[i] Y = X * X countPair + = countNum.get(Y, 0 ) return countPair # Driver code arr = [ 16 , 4 , 4 , 4 , 2 , 2 , 2 ] n = len (arr) # Function call print (countPairs(arr, n)) # This code is contributed by Tushar Rokade |
C#
// C# implementation of the code using System; using System.Collections.Generic; public class GFG { // Function to find count of pairs such that (X x X = Y) static int countPairs( int [] arr, int n) { int countPair = 0, X, Y; Dictionary< int , int > countNum = new Dictionary< int , int >(); // Store the element in the dictionary for ( int i = 0; i < n; i++) { if (countNum.ContainsKey(arr[i])) { countNum[arr[i]]++; } else { countNum.Add(arr[i], 1); } } // Check for element presence for ( int i = 0; i < n; i++) { if (arr[i] != 1) { X = arr[i]; Y = X * X; countPair += countNum.GetValueOrDefault(Y, 0); } } return countPair; } static public void Main() { // Code int [] arr = { 16, 4, 4, 4, 2, 2, 2 }; int n = arr.Length; // Function call Console.WriteLine(countPairs(arr, n)); } } // This code is contributed by sankar. |
Javascript
// Javascript Implementation of the code // Function to find count of pairs such // that (X x X= Y) function countPairs(arr) { let countPair = 0; let countNum = {}; // Store the element in the map for (let i = 0; i < arr.length; i++) { if (countNum[arr[i]]) { countNum[arr[i]]++; } else { countNum[arr[i]] = 1; } } // Check for element presence for (let i = 0; i < arr.length; i++) { if (arr[i] !== 1) { const X = arr[i]; const Y = X * X; if (countNum[Y]) { countPair += countNum[Y]; } } } return countPair; } // Driver code const arr = [16, 4, 4, 4, 2, 2, 2]; const n = arr.length; // Function call console.log(countPairs(arr)); // This code is contributed by Pushpesh Raj |
Output
12
Time Complexity: O(N)
Auxiliary Space: O(1)