#include #include #include using namespace std; /** * Problem: Geometric Triplets * Approach: Frequency maps (Hash Maps) to count potential left and right elements. * Time Complexity: O(n) * Space Complexity: O(n) */ long long countGeometricTriplets(int n, int r, vector& a) { unordered_map left_map; unordered_map right_map; // Fill the right map with the frequency of all elements for (long long x : a) { right_map[x]++; } long long total_triplets = 0; for (int j = 0; j < n; j++) { long long mid = a[j]; // Remove current element from right map so it's not counted as a 'k' index right_map[mid]--; // Check if mid can be the middle of a progression // 1. mid must be divisible by r to have a valid integer a_i // 2. a_i (mid/r) must exist in left_map // 3. a_k (mid*r) must exist in right_map if (mid % r == 0) { long long prev = mid / r; long long next = mid * r; if (left_map.count(prev) && right_map.count(next)) { total_triplets += left_map[prev] * right_map[next]; } } // Add current element to left map for future iterations left_map[mid]++; } return total_triplets; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, r; if (!(cin >> n >> r)) return 0; vector a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } cout << countGeometricTriplets(n, r, a) << endl; return 0; }

Submission #93

Source Code