Good evening! It is a nice Tuesday evening in the Twin Cities of Minneapolis and St. Paul. My work day is coming to an end and if possible would like to finish and publish this post. Let’s see how it goes.
The days are getting shorter as times goes by. One thing and the other and my wife and I decided to skip the midday walk today. Tomorrow is going to be quite busy for me. We should get back on our routine on Thursday.
I did not have enough time to finish this post yesterday so I will do so today!!!
Very early this morning I read an article in LinkedIn stating that Julio Velarde has accepted the position of Chairman of the Central Reserve Bank of Peru for a fourth 5-year term. I know Julio since we were kids while attending K-12 in the same class. After graduating from school each took separate directions. Julio went back to Peru after studying abroad and has been very successful at what he does. Julio, my best wishes in your current position!!!
On a separate note, I received and read an email message which reminded of my childhood and my mother drinking percolated coffee in the afternoons. She would start the process and will get the first drops of coffee out of the pot and after adding to it very hot water she would enjoy her coffee. We used to call it `ink` because it was a very dark cup of java.
Enough chit-chat and let’s get down to the main topic for this post.
Earlier this morning I decided on the HackerRank: Count Triplets problem. As usual, if you are interested after reading the requirements in this post, I suggest you take a look at the current problem description at HackerRank. With time problems seem to be edited and may change slightly.
You are given an array and you need to find number of tripets of indices (i, j, k) such that the elements at those indices are in geometric progression for a given common ratio r and i < j < k. Input Format: The first line contains two space-separated integers n and r, the size of arr and the common ratio. The next line contains n space-seperated integers arr[i]. Returns: int: the number of triplets - WRONG!!!
We are given an array for this problem. Once we get to the signature of the function in question we will see that we are given a list (not an array).
Our task is to count the number of triplets we can find in the specified list. The definition of a triple is explained in the HackerRank site. In a nutshell the indices for the three elements I, j and k must maintain the following order: I < j < k and the values must be in a `geometric progression` for a ratio `r` which we are also given.
Note that the requirements call for the function of interest to return an int value. The signature requires a long value.
// Complete the countTriplets function below.
static long countTriplets(List<Long> arr, long r) {
}
We are going to solve the problem using the Java programming language and the VSCode IDE on a Windows computer.
The signature for the function of interest specifies as input a list not an array and the returned value is a long not an int. I guess such inconsistencies came due to changes in the description of the problem.
The approach we will use is based on the observation that the triplet values must hold the following relation:
previous value: a / r current value: a next value: a * r a/r, a, a*r i j k
For the current value a, we must have a previous value a / r and a next value a * r. Each of these values will be associated with indices I, j and k as specified by the requirements.
For ease of use and performance, we will use two hash maps. The first will hold the count of the previous values and the second the count of the next values.
Since we are not using the on-line IDE provided by HackerRank we will have to develop a simple test scaffold that will collect and process the input data, call the function of interest and display the results.
4 4
1 4 16 64
main <<< r: 4
main <<< arr: [1, 4, 16, 64]
<<< nextMap: {16=1, 64=1, 1=1, 4=1}
<<< currentVal: 1
<<< nextMap:{16=1, 64=1, 1=0, 4=1}
<<< prevCount: 0 nextCount: 1
<<< sum: 0
<<< prevMap: {1=1}
<<< nextMap: {16=1, 64=1, 1=0, 4=1}
<<< currentVal: 4
<<< nextMap:{16=1, 64=1, 1=0, 4=0}
<<< prevCount: 1 nextCount: 1
<<< sum: 1
<<< prevMap: {1=1, 4=1}
<<< nextMap: {16=1, 64=1, 1=0, 4=0}
<<< currentVal: 16
<<< nextMap:{16=0, 64=1, 1=0, 4=0}
<<< prevCount: 1 nextCount: 1
<<< sum: 2
<<< prevMap: {16=1, 1=1, 4=1}
<<< nextMap: {16=0, 64=1, 1=0, 4=0}
main <<< ans: 2
5 5
1 5 5 25 125
main <<< r: 5
main <<< arr: [1, 5, 5, 25, 125]
<<< nextMap: {1=1, 5=2, 25=1, 125=1}
<<< currentVal: 1
<<< nextMap:{1=0, 5=2, 25=1, 125=1}
<<< prevCount: 0 nextCount: 2
<<< sum: 0
<<< prevMap: {1=1}
<<< nextMap: {1=0, 5=2, 25=1, 125=1}
<<< currentVal: 5
<<< nextMap:{1=0, 5=1, 25=1, 125=1}
<<< prevCount: 1 nextCount: 1
<<< sum: 1
<<< prevMap: {1=1, 5=1}
<<< nextMap: {1=0, 5=1, 25=1, 125=1}
<<< currentVal: 5
<<< nextMap:{1=0, 5=0, 25=1, 125=1}
<<< prevCount: 1 nextCount: 1
<<< sum: 2
<<< prevMap: {1=1, 5=2}
<<< nextMap: {1=0, 5=0, 25=1, 125=1}
<<< currentVal: 25
<<< nextMap:{1=0, 5=0, 25=0, 125=1}
<<< prevCount: 2 nextCount: 1
<<< sum: 4
<<< prevMap: {1=1, 5=2, 25=1}
<<< nextMap: {1=0, 5=0, 25=0, 125=1}
main <<< ans: 4
4 2
1 2 2 4
main <<< r: 2
main <<< arr: [1, 2, 2, 4]
<<< nextMap: {1=1, 2=2, 4=1}
<<< currentVal: 1
<<< nextMap:{1=0, 2=2, 4=1}
<<< prevCount: 0 nextCount: 2
<<< sum: 0
<<< prevMap: {1=1}
<<< nextMap: {1=0, 2=2, 4=1}
<<< currentVal: 2
<<< nextMap:{1=0, 2=1, 4=1}
<<< prevCount: 1 nextCount: 1
<<< sum: 1
<<< prevMap: {1=1, 2=1}
<<< nextMap: {1=0, 2=1, 4=1}
<<< currentVal: 2
<<< nextMap:{1=0, 2=0, 4=1}
<<< prevCount: 1 nextCount: 1
<<< sum: 2
<<< prevMap: {1=1, 2=2}
<<< nextMap: {1=0, 2=0, 4=1}
main <<< ans: 2
6 3
1 3 9 9 27 81
main <<< r: 3
main <<< arr: [1, 3, 9, 9, 27, 81]
<<< nextMap: {1=1, 81=1, 3=1, 9=2, 27=1}
<<< currentVal: 1
<<< nextMap:{1=0, 81=1, 3=1, 9=2, 27=1}
<<< prevCount: 0 nextCount: 1
<<< sum: 0
<<< prevMap: {1=1}
<<< nextMap: {1=0, 81=1, 3=1, 9=2, 27=1}
<<< currentVal: 3
<<< nextMap:{1=0, 81=1, 3=0, 9=2, 27=1}
<<< prevCount: 1 nextCount: 2
<<< sum: 2
<<< prevMap: {1=1, 3=1}
<<< nextMap: {1=0, 81=1, 3=0, 9=2, 27=1}
<<< currentVal: 9
<<< nextMap:{1=0, 81=1, 3=0, 9=1, 27=1}
<<< prevCount: 1 nextCount: 1
<<< sum: 3
<<< prevMap: {1=1, 3=1, 9=1}
<<< nextMap: {1=0, 81=1, 3=0, 9=1, 27=1}
<<< currentVal: 9
<<< nextMap:{1=0, 81=1, 3=0, 9=0, 27=1}
<<< prevCount: 1 nextCount: 1
<<< sum: 4
<<< prevMap: {1=1, 3=1, 9=2}
<<< nextMap: {1=0, 81=1, 3=0, 9=0, 27=1}
<<< currentVal: 27
<<< nextMap:{1=0, 81=1, 3=0, 9=0, 27=0}
<<< prevCount: 2 nextCount: 1
<<< sum: 6
<<< prevMap: {1=1, 3=1, 9=2, 27=1}
<<< nextMap: {1=0, 81=1, 3=0, 9=0, 27=0}
main <<< ans: 6
Each test case has two input lines. The first line holds the number of elements in the array and the second the `r` factor. We will ignore the number of elements in the array.
The second line will hold a set of number which we will put into a list (not an array) and use it as an argument for the function of interest.
Our test code displays the `r` value the contents of the list after it has been populated. It seems that all is well so far. We are now ready to call the function of interest.
The result is shown as the last entry for each test. The intermediate lines are there for us to be able to better follow the operation of the code. Please note that such intermediate output IS NOT PART OF THE SOLUTION!
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read first input line ****
String[] nr = br.readLine().trim().split(" ");
long r = Long.parseLong(nr[1]);
// **** read list of long values ****
List<Long> arr = Arrays.stream(br.readLine().trim().split(" "))
.map(Long::parseLong)
.collect(Collectors.toList());
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< r: " + r);
System.out.println("main <<< arr: " + arr);
// **** call the function of interest and display result ****
System.out.println("main <<< ans: " + countTriplets(arr, r));
}
Our test scaffold is quite simple. We open a buffered reader to read the values of interest. We then close the buffered reader. The arguments are then displayed. Finally we call the function of interest and display the result.
/**
* Calculate triplet value if present in tuples.
* Execution: O(n) - Space: O(n)
*/
static long countTriplets(List<Long> arr, long r) {
// **** initialization ****
long sum = 0L;
HashMap<Long, Long> prevMap = new HashMap<Long, Long>();
HashMap<Long, Long> nextMap = new HashMap<Long, Long>();
// **** populate the nextMap - O(n) ****
for (Long a : arr)
nextMap.put(a, nextMap.getOrDefault(a, 0L) + 1L);
// ???? ????
System.out.println("<<< nextMap: " + nextMap.toString());
// **** loop through the input list - O(n) ****
for (int i = 0; i < arr.size() - 1; i++) {
// **** current value ****
Long currentVal = arr.get(i);
// ???? ????
System.out.println("<<< currentVal: " + currentVal);
// **** for starters ****
long prevCount = 0L;
long nextCount = 0L;
// *** decrement count for currentVal in nextMap ****
nextMap.put(currentVal, nextMap.getOrDefault(currentVal, 0L) - 1L);
// ???? ????
System.out.println("<<< nextMap:" + nextMap.toString());
// **** update the counts ****
if (prevMap.containsKey(currentVal / r) && currentVal % r == 0)
prevCount = prevMap.get(currentVal / r);
if (nextMap.containsKey(currentVal * r))
nextCount = nextMap.get(currentVal * r);
// ???? ????
System.out.println("<<< prevCount: " + prevCount + " nextCount: " + nextCount);
// **** update sum ****
sum += prevCount * nextCount;
// ???? ????
System.out.println("<<< sum: " + sum);
// **** increment count for currentVal in prevMap ****
prevMap.put(currentVal, prevMap.getOrDefault(currentVal, 0L) + 1L);
// ???? ????
System.out.println("<<< prevMap: " + prevMap.toString());
System.out.println("<<< nextMap: " + nextMap.toString());
}
// **** return long (NOT int) answer ****
return sum;
}
We start initializing two hash maps. We will use the `prevMap` to keep track of previous values in the list and their counts / frequencies. We will also use the `nextMap` to keep track of next values in the list and their counts and frequencies. Recall what we said earlier. We need to generate triplets in which the values have special relationships. The previous will hold a / r, the current will hold a, and the next will hold the value a * r.
Since we have not processed a value in the list, we will start by inserting all values in the list into the `nextMap`.
Please note that the statements used to display information ARE NOT PART OF THE SOLUTION. You must remove them if you wish to modify this code and submit your version to HackerRank.
We now enter a loop in which we process each element in the list left to right.
The `prevCount` and `nextCount` variables will hold the number of times a value is present in the list previous and next as we traverse the list. We will use these values to update the sum of triplets we encounter.
We then update the count of the current value on the `nextMap`.
We update the values of `prevCount` and `nextCount` in order to update the sum of triplets.
The current value is then inserted in the `prevMap` and its value is set to one, or in case it is already there, we just increase its value.
When we are all set and done, we return the value of the `sum` variable as a Long, not as an int as was mentioned in the requirements.
I wonder if we could get the same results if we process directly a modified version of the list. I ran out of time and decided not to pursue such approach. If you have some time, please give it a try and let me know your findings.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different web sites (i.e., HackerRank, LeetCode).
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John