Given an odd positive integer N, which denotes the size of an N*N square matrix filled with 1s, the task is to find the minimum number of steps to move all the 1s to a single cell of the matrix where, in one step any 1 can be moved to any cell which is horizontally, vertically or diagonally adjacent to it.
Examples:
Input: N = 3
Output: 8
Explanation: All the 8 1s present in the boundary can be brought to the centre of the matrix in one step.
So total required steps = 8Input: N = 367
Output: 16476832
Explanation: The minimum number of steps required to put all the cookies in exactly one block of the tray is 16476832.
Approach: The problem can be solved based on the following observation.
To minimize the number of steps, all 1s should be moved to the centre of the matrix.
Any cell of the matrix is a part of ith zone if it’s distance from the centre is i (horizontally, vertically or diagonally).
All the elements from ith block can be moved to centre in i steps.See the image below for a better idea about zones. (Here zones of a 7*7 matrix are shown)
Follow the steps mentioned below to solve the problem using the above observation:
- Total number of possible zones X = N/2.
- Total number of cells in ith zone is 2 * i * 4 = 8*i.
- So, the total number of steps required to move all the 1s of ith zone to the centre is 8*i*i.
- Run a loop from i = 1 to X and:
- Calculate the total number of steps for ith zone using the above formula.
- Add it with the sum.
- Return the final sum as the answer.
Below is the implementation of the above approach.
C++
|
Time Complexity: O(X), where X is the number of zones present in the matrix
Auxiliary Space: O(1)