We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
This is based on the idea that, as we move through the array from the last to the first element, we use a dictionary keep track of the 'running' number of times each number has occurred.
We use a second dictionary to keep track of the 'running' number of times each pair of the form (x,rx) has occurred, where x is a number in the array.
If we encounter a number, say k, such that r*(k) = a number we encountered at least once before, then the number of additional pairs (k,rk)) that can be formed with that number increases by the number of times rk has been encountered before.
Finally, for each number y, we add to the count the number of pairs of the form (yr,yr^2) that have occurred so far, and return that count after scanning through the entire array from back to front.
We could reverse-engineer this idea to implement a version where we start scanning through the array from the front to back (i.e. the other way around).
If there is anything code-wise that you don't understand, please specify the exact parts that require clarification.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Count Triplets
You are viewing a single comment's thread. Return to all comments →
This is based on the idea that, as we move through the array from the last to the first element, we use a dictionary keep track of the 'running' number of times each number has occurred.
We use a second dictionary to keep track of the 'running' number of times each pair of the form (x,rx) has occurred, where x is a number in the array. If we encounter a number, say k, such that r*(k) = a number we encountered at least once before, then the number of additional pairs (k,rk)) that can be formed with that number increases by the number of times rk has been encountered before.
Finally, for each number y, we add to the count the number of pairs of the form (yr,yr^2) that have occurred so far, and return that count after scanning through the entire array from back to front.
We could reverse-engineer this idea to implement a version where we start scanning through the array from the front to back (i.e. the other way around).
If there is anything code-wise that you don't understand, please specify the exact parts that require clarification.