Last Updated: 12 Sep, 2021

Fill The Matrix

Hard

Asked in companies

Solve now

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]]

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

Solve now

Approaches

01 Approach

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)

Solve now

02 Approach

In this approach, we will fill the matrix by building the matrix from the inside out. There are 3 cases for the matrix.

N is odd
N is even
N is double even (divisible by 4)

We will create 3 functions fillMatrixEven(N), fillMatrixOdd(N), fillMatrixDoublyEven(N) where N is the given integer.

Algorithm:

In the function fillMatrixDoubleEven(n)
- Initialise a 2D array matrix of nxn size
- Iterate i from 0 to n -1
  - Iterate j from 0 to n - 1
    - Set matrix[i][j] as n*i + j + 1
- Iterate i from 0 to n -1
  - Iterate j from 0 to n - 1
    - If i % 4 is 0 or i % 4 is 3 and j % 4 is 1 and j % 4 is 2
      - Set matrix[i][j] as n * n + 1 - matrix[i][j]
    - If i % 1 is 0 or i % 4 is 2 and j % 4 is 0 and j % 4 is 3
      - Set matrix[i][j] as n * n + 1 - matrix[i][j]
- Finally return matrix
In the function fillMatrixOdd(n)
- Initialise a 2D array matrix of nxn size
- Set i as n / 2 and j as n - 1
- Set num as 1
- While num is less than n*n
  - If i is equal to -1 and j is equal to n
    - Set i equal to 0 and j equal to n - 2
  - Otherwise
    - If j is equal to n, set j equal to 0
    - If i is eqaul to -1 set i as n - 1
  - If matrix[i][j] is not equal to 0
    - Increase i by 1 and decrease j by 2
    - Continue the loop
  - Ohterwise, set matrix[i][j] as num
  - Decrease i by 1, increase j by 1
  - Increase num by 1
- Finaly return the matrix
In the function fillMatrixEven(n)
- Set k as n - 2 / 4
- Initialise a 2D array matrix of nxn size
- Set add as n*n / 4
- Set quarter as fillMatrixOdd(n/2)
- Iterate i from 0 to n / 2- 1
  - Iterate j from 0 to n / 2- 1
    - Set matrix[i][j] as quarter[i][j]
- Iterate i from 0 to n / 2- 1
  - Iterate j from 0 to n / 2- 1
    - Set matrix[i + n / 2][j + n / 2] as quarter[i][j]
- Iterate i from 0 to n / 2- 1
  - Iterate j from 0 to n / 2- 1
    - Set matrix[i][j + n / 2] as quarter[i][j]
- Iterate i from 0 to n / 2- 1
  - Iterate j from 0 to n / 2- 1
    - Set matrix[i][j + n / 2] as quarter[i][j]
- Iterate i from 0 to n / 2 - 1
  - Iterate j from 0 to k - 1
    - Set temp as matrix[i][j]
    - Set matrix[i][j] as matrix[i + n / 2][j]
    - Set matrix[i + n / 2][j] as temp
- Iterate i from 0 to n / 2 - 1
  - Iterate j from n - 1 to n - k
    - Set temp as matrix[i][j]
    - Set matrix[i][j] as matrix[i + n / 2][j]
    - Set matrix[i + n / 2][j] as temp
- Set temp as matrix[n / 4][0]
- Set matrix[n / 4][0] as matrix[n - 1 - n / 4][0]
- Set matrix[n - 1 - n / 4][0] as temp
- Set temp as matrix[n / 4][n / 4]
- Set matrix[n / 4][n / 4] as matrix[n - 1 - n / 4][n / 4]
- Set matrix[n - 1 - n / 4][n /4] as temp
- Finally return the matrix
If n is equal to 0 or 2, return Null
If n % 2 is 1
- Return fillMatrixOdd(n)
If n % 4 is 0
- Return fillMatrixDoublyEven(n)
Otherwise
- Return fillMatrixEven(n)In this approach, we will fill the matrix by building the matrix from the inside out. There are 3 cases for the matrix.

N is odd
N is even
N is double even (divisible by 4)

We will create 3 functions fillMatrixEven(N), fillMatrixOdd(N), fillMatrixDoublyEven(N) where N is the given integer.

Algorithm:

In the function fillMatrixDoubleEven(n)
- Initialise a 2D array matrix of nxn size
- Iterate i from 0 to n -1
  - Iterate j from 0 to n - 1
    - Set matrix[i][j] as n*i + j + 1
- Iterate i from 0 to n -1
  - Iterate j from 0 to n - 1
    - If i % 4 is 0 or i % 4 is 3 and j % 4 is 1 and j % 4 is 2
      - Set matrix[i][j] as n * n + 1 - matrix[i][j]
    - If i % 1 is 0 or i % 4 is 2 and j % 4 is 0 and j % 4 is 3
      - Set matrix[i][j] as n * n + 1 - matrix[i][j]
- Finally return matrix
In the function fillMatrixOdd(n)
- Initialise a 2D array matrix of nxn size
- Set i as n / 2 and j as n - 1
- Set num as 1
- While num is less than n*n
  - If i is equal to -1 and j is equal to n
    - Set i equal to 0 and j equal to n - 2
  - Otherwise
    - If j is equal to n, set j equal to 0
    - If i is eqaul to -1 set i as n - 1
  - If matrix[i][j] is not equal to 0
    - Increase i by 1 and decrease j by 2
    - Continue the loop
  - Ohterwise, set matrix[i][j] as num
  - Decrease i by 1, increase j by 1
  - Increase num by 1
- Finaly return the matrix
In the function fillMatrixEven(n)
- Set k as n - 2 / 4
- Initialise a 2D array matrix of nxn size
- Set add as n*n / 4
- Set quarter as fillMatrixOdd(n/2)
- Iterate i from 0 to n / 2- 1
  - Iterate j from 0 to n / 2- 1
    - Set matrix[i][j] as quarter[i][j]
- Iterate i from 0 to n / 2- 1
  - Iterate j from 0 to n / 2- 1
    - Set matrix[i + n / 2][j + n / 2] as quarter[i][j]
- Iterate i from 0 to n / 2- 1
  - Iterate j from 0 to n / 2- 1
    - Set matrix[i][j + n / 2] as quarter[i][j]
- Iterate i from 0 to n / 2- 1
  - Iterate j from 0 to n / 2- 1
    - Set matrix[i][j + n / 2] as quarter[i][j]
- Iterate i from 0 to n / 2 - 1
  - Iterate j from 0 to k - 1
    - Set temp as matrix[i][j]
    - Set matrix[i][j] as matrix[i + n / 2][j]
    - Set matrix[i + n / 2][j] as temp
- Iterate i from 0 to n / 2 - 1
  - Iterate j from n - 1 to n - k
    - Set temp as matrix[i][j]
    - Set matrix[i][j] as matrix[i + n / 2][j]
    - Set matrix[i + n / 2][j] as temp
- Set temp as matrix[n / 4][0]
- Set matrix[n / 4][0] as matrix[n - 1 - n / 4][0]
- Set matrix[n - 1 - n / 4][0] as temp
- Set temp as matrix[n / 4][n / 4]
- Set matrix[n / 4][n / 4] as matrix[n - 1 - n / 4][n / 4]
- Set matrix[n - 1 - n / 4][n /4] as temp
- Finally return the matrix
If n is equal to 0 or 2, return Null
If n % 2 is 1
- Return fillMatrixOdd(n)
If n % 4 is 0
- Return fillMatrixDoublyEven(n)
Otherwise
- Return fillMatrixEven(n)

Solve now