Cube of a matrix
Given an M x N sized 2D array 'MATRIX', return the (i * i + j * j) value for elements in which the sum of cube of digits of the element is equal to the element itself. Here, 'i' is the row number from ‘0’ to ‘M-1’, and 'j' is the column number from ‘0’ to ‘N-1’.

Note:

If no such number is present, return -1.

Input format:

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'.

Output format:

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.

Note:

You are not required to print the output, it has already been taken care of. Just implement the function.

Constraints:

1

Question

Cube of a matrix

Given an M x N sized 2D array 'MATRIX', return the (i * i + j * j) value for elements in which the sum of cube of digits of the element is equal to the element itself. Here, 'i' is the row number from ‘0’ to ‘M-1’, and 'j' is the column number from ‘0’ to ‘N-1’.

Note:

If no such number is present, return -1.

Input format:

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'.

Output format:

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.

Note:

You are not required to print the output, it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
1 <= M <= 100
1 <= N <= 50
1 <= ELEMENT <= 10^9

Time limit: 1 second

Accepted Answer

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

Space Complexity: O(n)Explanation:

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

Recursive stack uses space of the order ‘LENGTH’.

Time Complexity: OtherExplanation:

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).

Accepted Answer

Optimised 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. 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, call a function that calculates the sum of the cubes of the digit of the element. The function called works as follows:-
a. Set SUM=0 and store the value of the element in another variable ‘DUPLICATE’.
b. REMAINDER = ELEMENT%10; this statement extracts the last digit of the element.
c. SUM = SUM + POW(REMAINDER, 3); this statement cubes the last digit extracted in step 2.
d. ELEMENT = ELEMENT/10; this statement removes the last digit for further calculations.
e. Repeat steps 2 to 4 till element becomes 0;
f. If SUM == DUPLICATE, return the element, else return -1.

3. Add(i*i + j*j) to our answer vector/list, where ‘i’ is the row index and ‘j’ is the column index.

4. At last, return the answer list/vector if the list is not empty otherwise return list having only 1 element which is -1.

Space Complexity: O(1)Explanation:

O(1), as it uses constant space.

Time Complexity: OtherExplanation:

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).

Given an M x N sized 2D array 'MATRIX', return the (i * i + j * j) value for elements in which the sum of cube of digits of the element is equal to the element itself. Here, 'i' is the row number from ‘0’ to ‘M-1’, and 'j' is the column number from ‘0’ to ‘N-1’.

Note:

Input format:

Output format:

Note:

Constraints:

Top 42Gears Mobility Systems Mts1 interview questions & answers

Popular interview questions of Mts1