Count comparisons
You are given a 2-D matrix M of dimensions N x D. You have to decide ranking based on the given matrix, rankings are defined as follows:
- Index i is said to be ahead of index j in rankings if the first index at which element value differs in row M[i] and M[j] has a greater value in row M[i].
- If for index i and index j, all the elements in row M[i] and M[j] are the same, then rankings of index i and j are considered the same.
To find the ranking order for every pair (i, j) (1 ≤ i < j ≤ N), row M[i] and M[j] are linearly searched starting from the first element till ranking among them can be decided. Thus, the number of comparisons required for each pair belongs to the range 1 to D.
Task:
Determine the total number of comparisons required to find the ranking order for all the pairs (i, j) where 1 ≤ i < j ≤ N.
Note: 1-based indexing is used.
Example:
Assumptions:
- N = 5
- D = 2
- M = [[1, 2], [1, 3], [2, 1], [2, 3], [2, 1]]
Approach:
- Comparing pairs (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5) takes just 1 comparison each, as the very first elements in the rows are different. So the total number of comparisons in this case = 6.
- Comparing pairs (1, 2), (3, 4), (3, 5), (4, 5) takes 2 comparisons as the first elements are the same, and we need to compare the second elements. So the total number of comparisons in this case = 4 * 2 = 8.
Hence, total comparisons = 6 + 8 = 14.
Function Description:
Complete the `solve` function provided in the editor. This function takes the following 3 parameters and returns the total number of comparisons required:
- N: Represents the number of rows in matrix M
- D: Represents the number of columns in matrix M
- M: Represents the elements of matrix M
Asked in:
GOOGLE