Given an array arr[] of N integers. The task is to find the number of index quadruples (i, j, k, l) such that a[i], a[j] and a[k] are in AP and a[j], a[k] and a[l] are in GP. All the quadruples have to be distinct.
Examples:
Input: arr[] = {2, 6, 4, 9, 2}
Output: 2
Indexes of elements in the quadruples are (0, 2, 1, 3) and (4, 2, 1, 3) and corresponding quadruples are (2, 4, 6, 9) and (2, 4, 6, 9)
Input: arr[] = {1, 1, 1, 1}
Output: 24
A naive approach is to solve the above problem using four nested loops. Check for the first three elements if they are in AP or not and then check whether the last three elements are in GP or not. If both the conditions satisfy, then they increase the count by 1.
Time Complexity: O(n4)
An efficient approach is to use combinatorics to solve the above problem. Initially keep a count of the number of occurrences of every array element. Run two nested loops, and consider both elements to be the second and third numbers. Hence the first element will be a[j] – (a[k] – a[j]) and the fourth element will be a[k] * a[k] / a[j] if it is an integer value. Hence the number of quadruples using these two indexes j and k will be a count of the first number * count of fourth number with the second and third element being fixed.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the count of quadruplesint countQuadruples(int a[], int n){ // Hash table to count the number of occurrences unordered_map<int, int> mpp; // Traverse and increment the count for (int i = 0; i < n; i++) mpp[a[i]]++; int count = 0; // Run two nested loop for second and third element for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { // If they are same if (j == k) continue; // Initially decrease the count mpp[a[j]]--; mpp[a[k]]--; // Find the first element using common difference int first = a[j] - (a[k] - a[j]); // Find the fourth element using GP // y^2 = x * z property int fourth = (a[k] * a[k]) / a[j]; // If it is an integer if ((a[k] * a[k]) % a[j] == 0) { // If not equal if (a[j] != a[k]) count += mpp[first] * mpp[fourth]; // Same elements else count += mpp[first] * (mpp[fourth] - 1); } // Later increase the value for // future calculations mpp[a[j]]++; mpp[a[k]]++; } } return count;}// Driver codeint main(){ int a[] = { 2, 6, 4, 9, 2 }; int n = sizeof(a) / sizeof(a[0]); cout << countQuadruples(a, n); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{ // Function to return the count of quadruples static int countQuadruples(int a[], int n) { // Hash table to count the number of occurrences HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); // Traverse and increment the count for (int i = 0; i < n; i++) if (mp.containsKey(a[i])) { mp.put(a[i], mp.get(a[i]) + 1); } else { mp.put(a[i], 1); } int count = 0; // Run two nested loop for second and third element for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { // If they are same if (j == k) continue; // Initially decrease the count mp.put(a[j], mp.get(a[j]) - 1); mp.put(a[k], mp.get(a[k]) - 1); // Find the first element using common difference int first = a[j] - (a[k] - a[j]); // Find the fourth element using GP // y^2 = x * z property int fourth = (a[k] * a[k]) / a[j]; // If it is an integer if ((a[k] * a[k]) % a[j] == 0) { // If not equal if (a[j] != a[k]) { if (mp.containsKey(first) && mp.containsKey(fourth)) count += mp.get(first) * mp.get(fourth); } // Same elements else if (mp.containsKey(first) && mp.containsKey(fourth)) count += mp.get(first) * (mp.get(fourth) - 1); } // Later increase the value for // future calculations if (mp.containsKey(a[j])) { mp.put(a[j], mp.get(a[j]) + 1); } else { mp.put(a[j], 1); } if (mp.containsKey(a[k])) { mp.put(a[k], mp.get(a[k]) + 1); } else { mp.put(a[k], 1); } } } return count; } // Driver code public static void main(String[] args) { int a[] = { 2, 6, 4, 9, 2 }; int n = a.length; System.out.print(countQuadruples(a, n)); }}// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach # Function to return the count of quadruples def countQuadruples(a, n) : # Hash table to count the number # of occurrences mpp = dict.fromkeys(a, 0); # Traverse and increment the count for i in range(n) : mpp[a[i]] += 1; count = 0; # Run two nested loop for second # and third element for j in range(n) : for k in range(n) : # If they are same if (j == k) : continue; # Initially decrease the count mpp[a[j]] -= 1; mpp[a[k]] -= 1; # Find the first element using # common difference first = a[j] - (a[k] - a[j]); if first not in mpp : mpp[first] = 0; # Find the fourth element using # GP y^2 = x * z property fourth = (a[k] * a[k]) // a[j]; if fourth not in mpp : mpp[fourth] = 0; # If it is an integer if ((a[k] * a[k]) % a[j] == 0) : # If not equal if (a[j] != a[k]) : count += mpp[first] * mpp[fourth]; # Same elements else : count += (mpp[first] * (mpp[fourth] - 1)); # Later increase the value for # future calculations mpp[a[j]] += 1; mpp[a[k]] += 1; return count; # Driver code if __name__ == "__main__" : a = [ 2, 6, 4, 9, 2 ]; n = len(a) ; print(countQuadruples(a, n)); # This code is contributed by Ryuga |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG{ // Function to return the count of quadruples static int countQuadruples(int []a, int n) { // Hash table to count the number of occurrences Dictionary<int, int> mp = new Dictionary<int, int>(); // Traverse and increment the count for (int i = 0; i < n; i++) if (mp.ContainsKey(a[i])) { mp[a[i]] = mp[a[i]] + 1; } else { mp.Add(a[i], 1); } int count = 0; // Run two nested loop for second and third element for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { // If they are same if (j == k) continue; // Initially decrease the count mp[a[j]] = mp[a[j]] - 1; mp[a[k]] = mp[a[k]] - 1; // Find the first element using common difference int first = a[j] - (a[k] - a[j]); // Find the fourth element using GP // y^2 = x * z property int fourth = (a[k] * a[k]) / a[j]; // If it is an integer if ((a[k] * a[k]) % a[j] == 0) { // If not equal if (a[j] != a[k]) { if (mp.ContainsKey(first) && mp.ContainsKey(fourth)) count += mp[first] * mp[fourth]; } // Same elements else if (mp.ContainsKey(first) && mp.ContainsKey(fourth)) count += mp[first] * (mp[fourth] - 1); } // Later increase the value for // future calculations if (mp.ContainsKey(a[j])) { mp[a[j]] = mp[a[j]] + 1; } else { mp.Add(a[j], 1); } if (mp.ContainsKey(a[k])) { mp[a[k]] = mp[a[k]] + 1; } else { mp.Add(a[k], 1); } } } return count; } // Driver code public static void Main(String[] args) { int []a = { 2, 6, 4, 9, 2 }; int n = a.Length; Console.Write(countQuadruples(a, n)); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript implementation of the approach // Function to return the count of quadruples function countQuadruples(a, n) { // Hash table to count the // number of occurrences let mp = new Map(); // Traverse and increment the count for (let i = 0; i < n; i++) if (mp.has(a[i])) { mp.set(a[i], mp.get(a[i]) + 1); } else { mp.set(a[i], 1); } let count = 0; // Run two nested loop for second // and third element for (let j = 0; j < n; j++) { for (let k = 0; k < n; k++) { // If they are same if (j == k) continue; // Initially decrease the count mp.set(a[j], mp.get(a[j]) - 1); mp.set(a[k], mp.get(a[k]) - 1); // Find the first element using // common difference let first = a[j] - (a[k] - a[j]); // Find the fourth element using GP // y^2 = x * z property let fourth = (a[k] * a[k]) / a[j]; // If it is an integer if ((a[k] * a[k]) % a[j] == 0) { // If not equal if (a[j] != a[k]) { if (mp.has(first) && mp.has(fourth)) count += mp.get(first) * mp.get(fourth); } // Same elements else if (mp.has(first) && mp.has(fourth)) count += mp.get(first) * (mp.get(fourth) - 1); } // Later increase the value for // future calculations if (mp.has(a[j])) { mp.set(a[j], mp.get(a[j]) + 1); } else { mp.set(a[j], 1); } if (mp.has(a[k])) { mp.set(a[k], mp.get(a[k]) + 1); } else { mp.set(a[k], 1); } } } return count; } // Driver code let a = [ 2, 6, 4, 9, 2 ]; let n = a.length; document.write(countQuadruples(a, n)); </script> |
Output:
2
Time Complexity: O(N2), as we are using nested loops to traverse N*N times. Where N is the number of elements in the array.
Auxiliary Space: O(N), as are using extra space for the map.
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!
