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++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum number// of steps required to put// all the cookies in exactly one cellint minSteps(int N){ // Stores the minimum number of steps int res = 0; // Loop to iterate over // all the zones present in the matrix for (int i = 1; i <= N / 2; ++i) { // Steps to move all 1s of ith zone // to the centre of the matrix res += 8 * i * i; } // Return the minimum steps return res;}// Driver Codeint main(){ // Given input int N = 7; // Function Call cout << minSteps(N); return 0;} |
Java
// JAVA program for the above approachimport java.util.*;class GFG { // Function to find the minimum number // of steps required to put // all the cookies in exactly one cell public static int minSteps(int N) { // Stores the minimum number of steps int res = 0; // Loop to iterate over // all the zones present in the matrix for (int i = 1; i <= N / 2; ++i) { // Steps to move all 1s of ith zone // to the centre of the matrix res += 8 * i * i; } // Return the minimum steps return res; } // Driver Code public static void main(String[] args) { // Given input int N = 7; // Function Call System.out.print(minSteps(N)); }}// This code is contributed by Taranpreet |
Python
# Python program for the above approach# Function to find the minimum number# of steps required to put# all the cookies in exactly one celldef minSteps(N): # Stores the minimum number of steps res = 0 # Loop to iterate over # all the zones present in the matrix i = 1 while(i <= N//2): # Steps to move all 1s of ith zone # to the centre of the matrix res += 8 * i * i i += 1 # Return the minimum steps return res# Driver Code# Given inputN = 7# Function Callprint(minSteps(N))# This code is contributed by Samim Hossain Mondal. |
C#
// C# program for the above approachusing System;class GFG { // Function to find the minimum number // of steps required to put // all the cookies in exactly one cell static int minSteps(int N) { // Stores the minimum number of steps int res = 0; // Loop to iterate over // all the zones present in the matrix for (int i = 1; i <= N / 2; ++i) { // Steps to move all 1s of ith zone // to the centre of the matrix res += 8 * i * i; } // Return the minimum steps return res; } // Driver Code public static void Main() { // Given input int N = 7; // Function Call Console.Write(minSteps(N)); }}// This code is contributed by Samim Hossain Mondal |
Javascript
<script> // JavaScript program for the above approach // Function to find the minimum number // of steps required to put // all the cookies in exactly one cell const minSteps = (N) => { // Stores the minimum number of steps let res = 0; // Loop to iterate over // all the zones present in the matrix for (let i = 1; i <= parseInt(N / 2); ++i) { // Steps to move all 1s of ith zone // to the centre of the matrix res += 8 * i * i; } // Return the minimum steps return res; } // Driver Code // Given input let N = 7; // Function Call document.write(minSteps(N));// This code is contributed by rakeshsahni</script> |
112
Time Complexity: O(X), where X is the number of zones present in the matrix
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
