GOOGLE Coding Question – Solved

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