Cube of a matrix

The first line of input contains an integer ‘T’ denoting the number of test cases. The next ‘2T’ lines represent the ‘T’ test cases. The first line of each test case contains ‘M’ and ‘N’, denoting the number of rows and columns, respectively. The second line of each test case contains ‘M’ * ’N’ space-separated integers representing the elements of the 2D array 'MATRIX'.

For each test case, return (i * i + j * j) value for elements in which the sum of cube of digits of the element is equal to the element itself, where 'i' is the row number from ‘0’ to ‘M' - 1, and 'j' is the column number from ‘0’ to ‘N’ - 1.

Test case 1: The element at position A[0][0] is 1. The cube of the digits of 1 is 1^3 = 1, which is the element itself. Here i = 0 and j = 0 so we add (0*0 + 0*0) = 0 to our answer. The element at position A[1][2] is 370. The cube of the digits is also 370 (3^3 + 7^3 + 0^3 = 370), which is the element itself. Here i = 1 and j = 2 so we add 1*1 + 2*2 = 5 to our answer. While all the other elements do not satisfy the condition. Test case 2: The element at position A[1][3] is 153. The cube of digits is 1^3+5^3+3^3 = 153, which is the element itself. While all other elements do not satisfy the condition. Hence, the output is (1*1+3*3) = 10.

Sum of cube of digits of 2 = 2^3 = 8 ≠ 2 Sum of cube of digits of 4 = 4^3 = 64 ≠ 4 Sum of cube of digits of 6 = 6^3 = 216 ≠ 6 Sum of cube of digits of 18 = 1^3+8^3 = 513 ≠ 18 Since none of the elements among 2, 4, 6, 18 have the sum of the cube of digits as the number, it will return -1.

Brute Force approach

The idea is to traverse the matrix of size M x N. For each element in the matrix, we find the sum of the cube of their digits recursively. If the sum of the cube of digits is equal to the element itself, calculate (i*i + j*j).

Traverse the given matrix.
For each element in the matrix, store the value of the element in variable ‘DUPLICATE’ and call a function that calculates the sum of the cubes of the digit of the element. The function called works as follows:-
a. Set the base condition such that when the element becomes 0, it returns 0.
b. Take a variable ‘ANS’ which stores the sum of cubes of the digits.
c. With every recursion, add the cube of the last digit of the element to the sum using (ELEMENT%10)^3 and call the recursive function again by passing the rest of the element, that is, excluding the last digit using (ELEMENT/10).
d. When the base condition is hit, return the sum.
If SUM == DUPLICATE, ADD(i*i + j*j) to our answer vector/list, where ‘i’ is the row index and ‘j’ is the column index.
At last, return the answer list/vector if the list is not empty otherwise return list having only 1 element which is -1

Time Complexity

O(M * N * LENGTH), Where ‘M’ is the number of rows, ‘N’ is the number of columns and ‘LENGTH’ is the count of digits of the largest element.

Since here we traverse the M x N sized matrix and find the sum of the cubes of the digit which is equal to traversing the LENGTH i.e. the count of digits of the largest element. Therefore the complexity here grows by the order of O(M * N * LENGTH).

Space Complexity

O(LENGTH), where ‘LENGTH’ is the count of digits of the largest element.

Recursive stack uses space of the order ‘LENGTH’.

Problem statement

Sample input 1

Sample output 1

Explanation of sample input 1:

Sample input 2

Sample output 2

Explanation of sample input 2: