Thanks, I cleared all the test cases! Takeaways from my solution:

• I used two maps, one to keep count and one to track the number of potential triplets.
• Keeping track of the latter makes updating the result trivial.
• Only a single pass of the array was needed.
• No edge case condition when R is 1.

I highly recommend to anyone not quite understanding, think through the case

5 2
1 2 1 2 4

The expected answer is 3. I was getting 4 with my initial approach. Good luck!

You do need to consider (R == 1)

please share your code in c++ .

I tired your method but it is not working. Can you please share your code so that I can get to know that where did I go wrong?

Why does my code fail with R==1. Or any other hints appreciated.

static long countTriplets(long[] arr, long r) {
    HashMap<Long, Long> map1 = new HashMap();
    HashMap<Long, Long> map2 = new HashMap();
    long count = 0;
    for(int i = arr.length - 1; i >= 0; i--) {
        long a = arr[i];
        if(map1.containsKey(a*r)) {
            long c = map1.get(a*r);
            map2.put(a, map2.getOrDefault(a, 0L) + c);
        }

        if(map2.containsKey(a*r))
            count += map2.get(a*r);

        map1.put(a, map1.getOrDefault(a, 0L) + 1);  
    }
    return count;
}

I am stuck with the the corner case of R=1 , It will be great if you can share your solution.

Help...

this feels more like a hard problem > . < thanks for posting. glad i came across this.

The idea of using 2 hash map pointed me into the right direction, thank you :)

It was only after my first C++ solution passed all the test cases that I saw this comment in the discussion. It prompted me to refine my solution to eliminate the division and modulo operations. It seems necessary to make a small addition to the linear space factor to do so, and whether that extra space is worth the arithmetic complexity reduction seems like a weird trade-off in an algorithm that uses standard allocators.

after your hint made this Javascript solution

function countTriplets(arr, r) {
    let dict = {};
    let count = 0;
    arr.forEach(val=>{
        if (!dict[val]) {dict[val] = {s1:0,s2:0,s3:0};}
        if (!dict[val*r]) {dict[val*r] = {s1:0,s2:0,s3:0};}
        count += dict[val].s3;
        r===1 ? dict[val].s1 = 1 : dict[val].s1 += 1;
        dict[val*r].s3 += dict[val].s2;
        dict[val*r].s2 += 1;
    });
    return count;
}

These hints were great but I'm not sure what you were referring to with map(dict) -- I didn't use any mapping at all.

I ran a forward loop to find number of geometric-predecessors of each position in O(n) time.

Then I ran one last backward loop in O(n) time to find the number of geometric-successor of each position and adding the product of num predcessor and num successor to get the final result.

Hi please my code fails at test case 6 (not R ==1), any hints would be appreciated.

public static long countTriplets(List<Long> arr, long r) {
        HashMap<Long, Long> v1 = new HashMap<>();
        HashMap<Long, Long> v2 = new HashMap<>();

        long count = 0;

        for (Long digit : arr) {
            if (v2.containsKey(digit / r)) {
                count += v2.get(digit / r);
            }

            if (v1.containsKey(digit / r)) {
                long c = v1.get(digit / r);
                v2.put(digit, v2.getOrDefault(digit, 0L) + c);
            }
           
            v1.put(digit, v1.getOrDefault(digit, 0L) + 1);
        }
        return count;
    }

Thanks for the hints! Still had to struggle for a while after taking them in but managed to solve this problem eventually.

I read some other comments saying they used two maps but I also arrived at a correct solution using one map.

This took me a while, after all all your hints were very helpful, I just would add that you have to count instead of "keep track" to meet the performance requirements, and just 1 map is enough to get to the correct solution.

According to the constraints, multiplication may cause integer overflow in 32-bit platforms.

I need a C code?

Found your hints to be extremely helpful. Thanks for not putting the code here as it got me thinking and coming up with a solution. I still have 4 test cases that are timing out but getting much closer.

Thanks for your hints. I have to consider (r == 1) with my solution. How to optimize my solution so that I don't need to consider the corner case. Looking forward to your reply!

def countTriplets(arr, r):
    singleMap = {}
    doubleMap = {}
    tripleMap = {}
    for num in arr:
        # every number in this array can be the first number of triplets
        singleMap.setdefault(num, 0)
        singleMap[num] += 1

        # if it can be the second number of triplets
        if num % r == 0:
            first = num // r
            if first in singleMap:
                doubleMap.setdefault((first, num), 0)
                doubleMap[(first, num)] += singleMap[first]

        if num % r == 0 and num % (r * r) == 0:
            # it can be the third number in the triplets
            first, second = num // r // r, num // r
            if (first, second) in doubleMap:
                tripleMap.setdefault((first, second, num), 0)
                tripleMap[(first, second, num)] += doubleMap[(first, second)]

    if r == 1:
        return sum(map(lambda n: n * (n - 1) * (n - 2) // 6, singleMap.values()))

    return sum(tripleMap.values())

thanks, you were a big help.

Thanks for the hints, worked like a charm

Brilliant!!

can you share the code??

In fact, you need to consider r == 1, this hint made me loose a lot time :(

Test case 2, 3, 11 are with r == 1

In think what they meant, is that there is a solution where you dont need to do : if(r == 1)

It keeps timing out. I understand my solution is cubic but how do i get it faster.... :(

Here is my solution:

import java.io.; import java.math.; import java.security.; import java.text.; import java.util.; import java.util.concurrent.; import java.util.function.; import java.util.regex.; import java.util.stream.*; import static java.util.stream.Collectors.joining; import static java.util.stream.Collectors.toList;

public class Solution {

// Complete the countTriplets function below.
static long countTriplets(List<Long> arr, long r) {
    long result = 0;

    Map<Long, Map<Long, Long>> triplet = new HashMap<>();
    Map<Long, Long> pairProgression = new HashMap<>();
    Map<Long, Long> placeHolder = new HashMap<>();
    long pH = -1000;
    long secondValue = -1000;
    long thirdValue = -1000;
    triplet.put(pH, placeHolder);

    for(long i = 0; i < arr.size(); i++){
       secondValue = -1000;
       thirdValue = -1000;
       int firstValueIndex = (int) i;
       long firstArrayValue = arr.get(firstValueIndex);
       //System.out.print("First Values : "+firstArrayValue);
       for(long j = i + 1; j < arr.size() ; j++){  
            int secondValueIndex = (int) j;
            long secondArrayValue = arr.get(secondValueIndex);
            long secondValueExpected = firstArrayValue * r;

            if(secondArrayValue == secondValueExpected ) {
            for(long k = j + 1; k < arr.size(); k++){
                int thirdValueIndex = (int) k;
                long thirdArrayValue = arr.get(thirdValueIndex);
                long thirdValueExpected = secondArrayValue * r;

                // System.out.println(firstArrayValue);
                // System.out.println(secondArrayValue+"  "+secondValueExpected);
                // System.out.println(thirdArrayValue+"  "+thirdValueExpected); 
                // System.out.println("                            ");
                if(secondArrayValue == secondValueExpected && thirdArrayValue == thirdValueExpected){
                    Map<Long, Long> pair = new HashMap<>();
                    pair.put( j, k);
                    triplet.put(i, pair);
                    result++;
                }      
            }
         }
       }

    }

    // For iterating through array - IK
    // for (Map.Entry<Long, Map<Long, Long>>entry : triplet.entrySet()) {
    //     Long key = entry.getKey();
    //     System.out.println(key);
    // }

    //System.out.println(r);
    return result;
}

public static void main(String[] args) throws IOException {
    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    String[] nr = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

    int n = Integer.parseInt(nr[0]);

    long r = Long.parseLong(nr[1]);

    List<Long> arr = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
        .map(Long::parseLong)
        .collect(toList());

    long ans = countTriplets(arr, r);

    bufferedWriter.write(String.valueOf(ans));
    bufferedWriter.newLine();

    bufferedReader.close();
    bufferedWriter.close();
}

}

Here's a JavaScript solution based on RobertsN's excellent idea.

const triplets = (arr, r) => {
    let r2 = {};
    let r3 = {};

    return arr.reduce((c, v) => {
        if (r3[v]) {
            c += r3[v];
        }

        if (r2[v]) {
            r3[v*r] = (r3[v*r] || 0) + r2[v];
        }

        r2[v*r] = (r2[v*r] || 0) + 1;
        return c;
    }, 0);
}

please provide link

want cpp code

100% accurate guidance. Really helpful. Thanks a lot. Some more hints: - 2 dict/map use helps it get easier. - order in which you update your dict determines whether to consider r=1 as corner or not.

Took a lot of time to figure out the O(n)-time O(n)-space solution, no corner cases, very simple code. At the end it's very beautiful.

I can't figure out what I'm doing partially wrong. I mean I cleared all the cases, but I had to consider r==1 as a special case:

    HashMap<Long, Long> counter2 = new HashMap<Long, Long>();
    HashMap<Long, Long> counter3 = new HashMap<Long, Long>();
    long tot = 0;

    for (Long elem : arr) {
        counter2.put(elem * r, counter2.getOrDefault(elem * r, 0l) + 1l);
        if (counter2.containsKey(elem)) {
            counter3.put(elem * r, counter3.getOrDefault(elem * r, 0L) + counter2.get(elem));
        }
        tot += counter3.getOrDefault(elem, 0L);
    }

    if (r == 1l) {
        Long tot_r1 = 0l;
        for (Long count : counter2.values()) {
            tot_r1 += count * (count - 1) * (count - 2) / 6l;
        }
        return tot_r1;
    }
    return tot;

How do you avoid the r==1 case?

Thank you. I hadn't realized the arrays were not sorted (need to stop assuming things when it's not stated!) After a point - I gave up on trying to look for, and keeping record of numbers...and start keeping track of sequences. That worked much better!

I came up with the solution with two maps, one to track the potentail Triplets with the first one element matched and one to track the potential Triplets with the first two elements matched, but my code failed with the R==1 edge case. Could any one help me with that?

please help me can I solve this question without using map i suffer the problem of time

Hi, can you help me what i am missing in below code as only 4 cases are failing.

include

using namespace std;

int max(int a,int b,int c) { int temp=0; if(a>b) { temp=a; } else { temp=b; } if(temp>c) { return temp; } else { return c; } }

// Complete the countTriplets function below. long countTriplets(int arr[], int r, int n) { map mp; for(int i=0;i

int m=mp.size(), res=0;
if(r==1)
{
    res=((mp[1])*(mp[1]-1)*(mp[1]-2))/(3*2);
}
else if(m>2)
{
for(int j=0;j<m-1;j++)
{        
   // cout<<mp[pow(r,j)]<<" ";
    if(mp[pow(r,j)] && mp[pow(r,j+1)] && mp[pow(r,j+2)])
    {
        res=res+(mp[pow(r,j)]*mp[pow(r,j+1)]*mp[pow(r,j+2)]);
    }
    else
    {
        continue;
    }

}

}
else
{
    return 0;
}

return res; }

int main() { int n,r; cin>>n; cin>>r; int a[n]; for(int i=0;i>a[i]; } long b=countTriplets(a,r,n); cout<

Also, can you share you code with proper explaintation.

Thanks in advance:)

Thanks for the hints. It took me lots of submissions to get it right though. What a clever way to solve this problem.

There is at least one test case which specifically tests for r == 1. So this is a corner case which clearly has to be considered

below code is giving runtime error? def countTriplets(arr, r):

my_list = []
for i in arr:
    my_list.append(int(math.log(i,r)))

comb = list(combinations(my_list,3))
counter = 0
for i in comb:
    if (i[0]==i[1]-1==i[2]-2):
        counter += 1
return counter

amazing thoughts

Thank you for the Tips bro.

Another approach that resembles the popular one here. It enumerates the array backward and builds an imaginable graph of connections a --> a*r --> a*r*r. But instead of building an actual graph it just accumulates statistics of nodes connections. That approach takes O(N), too, but utilizes a single map only! R = 1 is processed in a general way, too. C++14 code is down below:

long countTriplets(vector<long> arr, long r) {
    long total = 0;
    map<long, pair<long, int>> stats;
    for (auto it = arr.crbegin(); it != arr.crend(); ++it) {
        long child_transit;
        int child_own;
        tie(child_transit, child_own) = stats[*it*r];
        long our_transit;
        int our_own;
        tie(our_transit, our_own) = stats[*it];
        stats[*it] = make_pair(our_transit + child_own, our_own + 1);
        total += child_transit;
    }
    return total;
}

Great explanantion!