Count Triplets Hacker Rank Problem Solution

Count Triplets Hacker Rank Problem Solution->


Problem Statement->

You are given an array and you need to find number of tripets of indices  such that the elements at those indices are in geometric progression for a given common ratio  and .

For example, . If , we have  and  at indices  and .

Function Description

Complete the countTriplets function in the editor below. It should return the number of triplets forming a geometric progression for a given  as an integer.

countTriplets has the following parameter(s):

  • arr: an array of integers
  • r: an integer, the common ratio

Input Format

The first line contains two space-separated integers  and , the size of  and the common ratio.
The next line contains  space-seperated integers .

Constraints



 

My Code->



#include <bits/stdc++.h>


using namespace std;


string ltrim(const string &);

string rtrim(const string &);

vector<string> split(const string &);



// Complete the countTriplets function below.

long countTriplets(vector<long> arr, long r) {

   // arr.sort(arr.begin(),arr.end());


    map<long long int  ,long long int > lmap;

    map<long long int  ,long long int > rmap;

    for(int i=0;i<arr.size();i++){

       rmap[arr[i]]++;

    }

    long long int  count=0;

    for(int i=0;i<arr.size();i++){

        long long int  f=arr[i]/r;

        long long int s=arr[i];

        long long int t=arr[i]*r;

         rmap[arr[i]]--;



           if(arr[i]%r==0){

               count+=lmap[f]*rmap[t];


           }


            lmap[arr[i]]++;

           //cout<<"inside";






    }

    return count ;



}


int main()

{

    ofstream fout(getenv("OUTPUT_PATH"));


    string nr_temp;

    getline(cin, nr_temp);


    vector<string> nr = split(rtrim(nr_temp));


    int n = stoi(nr[0]);


    long r = stol(nr[1]);


    string arr_temp_temp;

    getline(cin, arr_temp_temp);


    vector<string> arr_temp = split(rtrim(arr_temp_temp));


    vector<long> arr(n);


    for (int i = 0; i < n; i++) {

        long arr_item = stol(arr_temp[i]);


        arr[i] = arr_item;

    }


    long ans = countTriplets(arr, r);


    fout << ans << "\n";


    fout.close();


    return 0;

}


string ltrim(const string &str) {

    string s(str);


    s.erase(

        s.begin(),

        find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))

    );


    return s;

}


string rtrim(const string &str) {

    string s(str);


    s.erase(

        find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),

        s.end()

    );


    return s;

}


vector<string> split(const string &str) {

    vector<string> tokens;


    string::size_type start = 0;

    string::size_type end = 0;


    while ((end = str.find(" ", start)) != string::npos) {

        tokens.push_back(str.substr(start, end - start));


        start = end + 1;

    }


    tokens.push_back(str.substr(start));


    return tokens;

}


Comments

Popular posts from this blog

जिओ टीवी jio tv की मदद से मोबाइल पर देखें टीवी ।। how to use jio tv

What is pixels || पिक्सल क्या होते हैं?

how touch screen works || टच स्क्रीन क्या है ? टच स्क्रीन कैसे काम करती है ?