There is a question from this challenge.
Can someone explain the logic of this solution.
Well, this was my solution.
Here goes the Logic.
Consider the array- [4, 2, 6, 3, 2, 5, 1].
The contiguous sub-arrays are
4
4 2
4 2 6
4 2 6 3
4 2 6 3 2
4 2 6 3 2 5
4 2 6 3 2 5 1
and so on. (Please draw all the sub-arrays on a sheet of paper). This is a reason for which I gave this array to you. Basically it contains duplicates and intersection points (which I explain further) as well.
Also To avoid unnecessary calculates, i.e. just to make solution faster by avoiding for loop in some cases, I used the condition a[p2] > k, which makes sense as maximum value of x%y is y-1 and minimum value is 0. What p1, p2 and path means is explained below. Consider K=1 for now. Similarly check for K=0 on your own on piece of paper. If you have further doubts after the complete explanation of mine, you can comment below.
One more thing to note down is that the minimum answer is ‘n’ for all cases. As the sub-arrays with only single element cannot contain a pair, forget about bad pairs. This was pretty obvious. 
Here p1 refers to the 1st pointer pointing to some array element and p2 refers to another pointer which points to another array element. Also p2>=p1 in the solution. The variable pair stores for given y, refered as a[p2] in my solution, the largest index or the nearest element in array ‘a’ for given y for which x%y==k. The variable maximum stores the maximum found in the array till that moment. Also, hash array is used to store the last index of the particular element traversed so far. For example, for element 2 the hash was initially -1, then 1 and finally 4 at the end. Since the maximum value possible was 10^5 for the array elements, using hash array was no problem. Otherwise we could have used ‘map’ STL or ‘multimap’ STL for C++ library which was earlier used by me to get 100 points.
Let’s now construct our answer one by one form p1, p2 and hash array.
Initially p1=0, p2=0 and path = -1.
while (pair<p1) was performed to check if any pair contains
maximum is initially set to 4 and no further action was required. p2 now points to the first element. Since a[p2] = 2 and a[p2]>k, we try to use the property that x%y=k implies x = c*y+k for c>=0 and the place till where we have to check for values of c is determined by the maximum value found in the array so far. So we check for values 1, 3 (as maximum was 4 till now). Since these were not present, no action was performed. This was continued till pointer p2 reached the element 3 (at index 3). Since here x = 1, 4 and since hash[4]!=-1 and pair(-1)<hash[4] and also hash[4]>=p1(0), so the pair (4,3) was found and pair stored the value 0. And the while loop terminated. So the number of good pairs found were p2-p1 = 3-0 = 3.
These pairs were actually 4, 4 2, 4 2 6. Since all the further pairs contain the pairs (4,3) and many more, which I don not need to consider as per my solution, and hence these sub-arrays will not be conted for our final answer.
Now, p1 advances to 1. Also, p2 is presently 3(pointing to element 3). Now the above same process is repeated till p2 reaches 4. So now, p2 points to element 2. Now the loop for x is again called with x = 1, 3. Since hash[3]!=-1 and pair(0)<hash[3] and hash[3]>=p1(1) , the pair was set to hash[3] i.e. 3, meaning pair (3,2) was found. Thus while loop terminated. To the sum was added p2-p1 = 4-1 = 3 i.e. the sub-arrays, 2, 2 6, 2 6 3. Since further sub-arrays will contain the pair (3,2) and hence will not contribute towards the final answer. Again we do not consider whether more bad pair were found for these sub-arrays as the sub-array is not counted even when one bad pair is found and all the sub-arrays contain this bad pair are excluded.
Now, p1 advances to 2. Pair is now 3 so, so while loop is not executed. Now, to the sum is added p2-p1=4-2=2 sub-arrays namely 6, 6 3. Now p1 advances to 3 and to the sum is added p2-p1=4-3=1 sub-array which is 6 and p1 advances to 4. the sum remains unaffected as we add 0 to it.
Till now the sum is 3+3+2+1=9.
Now p1 advances to 5. Also, the maximum found till now was 6. Thus pair(4)<p1(5), while loop is executed. Now p2 points to 5. Since the for loop is executed, x=1, 6. pair was set to 2 i.e. pair (6,5) was created. p2 now points to the final element 1 for which no pair was found. Since, p2 now equal n, to the sum (in the final step) we add all the remaining good combinations beginning with 2. i.e. 2, 2 5, 2 5 1, 5, 5 1, 1 and the final answer is 9+6 = 15.
In short, basically what I did was to cancel the create the sub-arrays column wise i.e. starting from particular element and cross all the sub-arrays which contain a bad pair. When p2 reached ‘n’ so more bad pair can be formed and we can safely caluculate the final remaining sub-arrays for the sum and print that ‘sum’ as the answer.
Column- wise generation of sub-arrays
4, 4 2, 4 2 6, 4 2 6 3, 4 2 6 3 2, 4 2 6 3 2 5, 4 2 6 3 2 5 1
2, 2 6, 2 6 3, 2 6 3 2, 2 6 3 2 5, 2 6 3 2 5 1
6, 6 3, 6 3 2, 6 3 2 5, 6 3 2 5 1
3, 3 2, 3 2 5, 3 2 5 1
2, 2 5, 2 5 1
5, 5 1
1
So in the first column starting with 4, all the arrays which contain (4,3) found as the first bad pair were cancelled i.e. (4 2 6 3, 4 2 6 3 2, 4 2 6 3 2 5, 4 2 6 3 2 5 1).
Now in the second list, all the sub-arrays containing (3,2) as the next bad pair found were removed.
(2 6 3 2, 2 6 3 2 5, 2 6 3 2 5 1, 6 3 2, 6 3 2 5, 6 3 2 5 1, 3 2, 3 2 5, 3 2 5 1) Here , in this example in by this step we had removed all the sub-arrays containing the bad pairs.
Since we were interested in calculating the remaining sub-arrays we added the remaining ones to our answer. i.e 3 from first one, 3 from next one, 2 from next one, 1 from next one and finally all the remaining 6 from the next one. This was just the way sum was calculated and finally printed as the answer.
To understand the concept more, you the debug the above program for the same array but for K=0 yourself on a piece of paper. If there are still more doubts, feel free to ask.
Hope, it helped. (Was just amazing feeling to see the solution pass in 0.00 second).
7 Likes
Just do not forget to cast your votes, if you liked the solution and its explanation
This is what I thought:
A bad pair (a,b) follows the relation a = q*b + r. ‘r’ is the remainder after dividing ‘a’ with ‘b’, and ‘q’ is the corresponding divisor.
One thing to notice is that for ‘a’ mod ‘b’ == ‘k’, ‘b’ should be greater than ‘k’ (‘b’>‘k’), because value of ‘x’ mod ‘y’ is always between 0 and ‘y’-1. Also, ‘a’ should be greater than or equal to ‘k’, because remainder after dividing with a number is always less than or equal to it.
For any two numbers ‘a’ and ‘b’ in the given array, if they are to form a bad pair they have to satisfy the above relation ( a = qb + r) with ‘r’ = ‘k’. Therefore, if we mark the numbers 0b + k, 1b + k, 2b + k, 3b + k, 4b + k, …(up to the maximum number or 10^5), in the flag array and check if any number ‘a’ has flag[a] also marked, then (a,b) is a bad pair.
Also, in the bad pair (a,b), ‘a’ is on left and ‘b’ is on right, so we can start from the end and if flag[ ar[i] ] is not marked, then it does not form a bad pair with any index greater than it.
While marking the flag array, we will update the flag array with the index of the current ‘b’. If we are at some value ‘x’ in the array with index ‘i’, if flag[x] is marked and suppose it has a value ‘y’ (let value at index ‘y’ be ‘z’ { (x,z) will form a bad pair } ) , then the maximum number of sub arrays that the bad pair(x,z) will not be a part of will be (y-i).
Why maximum?
Suppose we are at index 5 at the moment, and its bad pair is at index 11. If the bad pair of index 6 was at index 8, then number of sub arrays that the value at index 5 and its bad pair, will not be a part of are not (11-5), but (8-5).
Therefore, we have to keep track of the minimum left most index so that no bad pairs are involved between that index and the index we are currently at.
So we have 3 cases for any index:
-
For any index i, if ar[ i ] is greater than k, find its bad pair, if any, by checking flag[ ar[ i ] ]. If it is -1 ( the value with which the flag array is initialized), then it is not a part of any bad pair whose index is greater than i. The answer of this case is simply ( the current left most index - i). Now, we mark the flag array for this value.
-
If ar[ i ] == k, then it cannot be a ‘b’ ( as ‘b’ > k), we do not have to mark the flag array in this case, we just need to check if it forms a bad pair by checking if flag[ ar[ i ] ] is marked. If it is, and is less than the current minimum, we update it and add to the answer (current minimum - i).
-
If ar[ i ] is less than ‘k’, we DO NOT need to check in the flag array and simply add (minimum - i) to our answer.
4 Likes
Sorry @likecs and @rishivikram,
both of your solutions are O(n^2) worst case. Both time out for similar testcases: small K, many small numbers in large array, but one huge number.
For example:
`N=100000 K=0
A[i]=2 for i!=0
A[0]=100000
Test cases for this problem were far to weak, but everybody should better stick to the official solution which gives AC under any circumstances.
Reason for checking hash[x]>= p1.
Since we just want the pair to store the nearest value for which x%y==k and also the sub-array counting should atleast start from p1. i.e. if p1 was pointing to index 1 (element 2) so the pair (4,3) should not be considered again. For example in case the array was [4, 3, 3] we should only consider the first pair (4,3) and when p1 advances to 1, we should not consider the pair (4,3) as we have already removed all the sub-arrays which contain (4,3) as the first pair. So the correct answer in this case is 1+1+2=4 (subarrays are 4, 3, 3 3, 3)
You’re welcome 