Fill The Matrix

Hard
0/120
Average time to solve is 45m
profile
Contributed by
4 upvotes
Asked in companies
Goldman SachsGoogle inc

Problem statement

You are given an integer ‘N’. You have to return a matrix of ‘N’ rows and ‘N’ columns formed from integers 1 to N*N, such that the sum of each row, column, and two diagonals are equal. If it’s not possible, you have to return an empty array.

For Example: 
 You are given ‘N’ = 3,  the matrix formed such that sum of rows, columns, and two diagonals are equal is
[[8, 3, 4],
 [1, 5, 9]
 [6, 7, 2]]
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
 The first line of input contains the integer ‘T’ representing the number of test cases.

The first line of each test case contains the single integer ‘N’ representing the given integer.
Output Format: 
For each test case, print ‘CORRECT’ if the returned matrix is correct, print ‘NULL’ if it’s impossible to form the matrix with the given number.

Print a separate line for each test case.
Constraints: 
1 <= T <= 10
1 <= N <= 1000

Time Limit: 1 sec
Sample Input 1:
2
2
3
Sample Output 2:
NULL
CORRECT
Explaination:
For the first test case, N = 2, we have to make the matrix with 1 2 3 4, which is impossible with the given conditions; hence the answer is NULL.

For the second test case N = 3, one of the matrices formed such that the sum of rows, columns, and two diagonals are equal is
[[8, 3, 4]
 [1, 5, 9]
 [6, 7, 2]]
Sample Input 2:
1
4
Sample Output 2:
CORRECT
Explanation:
For the test case n = 4, one of the matrices formed such that the sum of rows, columns, and two diagonals are equal is 
[[16, 2, 3, 13],
 [5, 11, 10, 8],
 [9, 7, 6, 12],
 [4, 14, 15, 1]]
Hint

Try to use backtracking. 

Approaches (2)
Backtracking

In this approach, we will try to place every available number at a current position and check if the matrix is valid. We will keep track of the number we have already placed, so we don’t place twice.

 

We will create two functions checkFunction(ans) to check if the ans matrix is valid. fillMatrixUilt(n, mat, nums, row, col) is the backtracking function, where n is the number given, mat is the matrix. array keeps track of the used numbers and row, col is the current row and column of the matrix.

 

Algorithm:

  • The checkFunction(ans)
    • Set currSum as the sum of array ans[0]
    • Iterate row through ans
      • If currSum is not equal to the sum of the array row
        • Return false
    • Iterate i from 0 the size of ans - 1
      • Set s as the sum of all values ans[j][i] where j is from 0 to size of ans - 1
      • If s is not equal to currSum return False
    • Set diagr as the sum of the right diagonal of ans
    • Set diagl as the sum of the left diagonal of ans
    • If diagr is not equal to diagl return false
    • If diagl is not equal to currSum return false
    • Return True
  • The function fillMatrixUtil(n, mat, nums, row, col)
    • If col is equal to n and row is equal to n -1
      • Return mat if checkFunction(mat) is true else return empty array
    • If col is equal to n
      • Then return fillMatrixUtil(n, mat, nums, row + 1, 0)
    • Iterate i from 0 to n*n - 1
      • If  nums[i] equals 1 continue the loop
      • Set nums[i] as 1
      • Set mat[i][j] as i + 1
      • Set ans equal to fillMatrixUtil(n, mat, nums, row, col + 1)
      • If the size of ans is greater than 0, then return ans
      • Set nums[i] as 0
      • Set mat[row][col] as  0
    • Return an empty array
  • Set nums as an array of 0 of size n*n
  • Set mat as a 2-D matrix of nxn size
  • Return fillMatrixUtil(n, mat, nums, 0, 0)
Time Complexity

O((N^2) ^ (N^2))), where N is the given number.

 

For the element of the matrix, we are trying to place 1 to N^2 number, which will cost O((N^2) ^ (N^2))) time. Hence the final time complexity is O((N^2) ^ (N^2))).

Space Complexity

O(N^2), Where N is the given number.

 

We are maintaining a 2-D matrix that takes O(N^2) space. The recursion stack also takes O(N^2) space. Hence the final space complexity is O(N^2).

Code Solution
(100% EXP penalty)
Fill The Matrix
Full screen
Console