POWER3 - Editorial

editorial
1

PROBLEM LINK:

Practice
Author: (codechefnitj | CodeChef User Profile for Codechef NITJ Chapter | CodeChef)
Editorialist: Amritdeep Singh

DIFFICULTY:

MEDIUM

PREREQUISITES:

None

PROBLEM:

In the above problem we have to find the pair of indexes in an array such that sum of them is a power of three

EXPLANATION:

So, the brute force solution would be checking each and every pair of indexes that will give sum a power of three. Time complexity of this solution will be O(N^2) which will will not work for the given constraint of N so we have to come with a different approach. What we can do to solve our problem is first of all store every element in the map which will have key as the number and value as the frequency of that number in the array. Now, rather searching for the pairs which will give sum as a any power of 3 we will just do it’s reverse!, we will take a number which is a power of three eg. 3^0,3^1,3^2.. let’s say X and now choose a key let’s say Key and search for X-Key in the map if we find that key can easily find possible pairs by freq(Key)* freq(X-Key). Be careful ! when we check for all the Keys we will count each possible pair twice se our final answer will be total pairs divided by 2.

TIME COMPLEXITY:

as we are traversing the map and map operations require O(logN) and in worst case the size of map will be N so the time complexity will be O(NlogN)

SOLUTIONS:

Editorialist's Solution 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define And &&
#define Or ||
#define space
#define int long long
#define vi vector<int>
#define pb(n) push_back(n)
#define mii map<int, int>
#define test_cases_loop \
    int t;              \
    cin >> t;           \
    while (t--)
#define FIO                           \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);
#define loop(var, initial, final) for (int var = initial; var < final; var++)

int32_t main()
{
    int n;
    cin >> n;
    map<int, int> freq;
    int maxi = INT_MIN;
    loop(i, 0, n)
    {
        int x;
        cin >> x;
        maxi = max(maxi, x);
        freq[x]++;
    }
    int a = 1;
    int ans = 0;

    while (a <= 2 * maxi)
    {

        for (auto i : freq)
        {
            int key = i.first, freq_of_key = i.second;
            int num_to_find = a - key;

            if (freq.find(num_to_find) != freq.end())
                ans += freq_of_key * freq[num_to_find];
        }

        a *= 3;
    }
    cout << ans / 2 << endl;

    return 0;
}
1 Like