fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int countDiscountEligiblePairs(const vector<int>& price) {
  6.     // Step 1: Precompute powers of 3 up to 2 * 1e9
  7.     unordered_set<long long> powersOfThree;
  8.     long long p = 1;
  9.     while (p <= 2e9) {
  10.         powersOfThree.insert(p);
  11.         p *= 3;
  12.     }
  13.  
  14.     // Step 2: Count pairs using hashmap
  15.     unordered_map<int, int> freq;
  16.     int count = 0;
  17.  
  18.     for (int p : price) {
  19.         for (long long power : powersOfThree) {
  20.             long long complement = power - p;
  21.             if (complement >= 1 && complement <= 1e9 && freq.count(complement)) {
  22.                 count += freq[complement];
  23.             }
  24.         }
  25.         freq[p]++;
  26.     }
  27.  
  28.     return count;
  29. }
  30.  
  31.  
  32. int main() {
  33. 	// your code goes here
  34. 	int n;
  35. 	cin >> n;
  36. 	vector<int> prices(n);
  37. 	for (int i=0;i<n;i++) cin >> prices[i];
  38. 	cout << countDiscountEligiblePairs(prices) << '\n';
  39. 	return 0;
  40. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin 
2
4 23
stdout 
1
https://ideone.com/FK2JFn
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!