You have an NxN grid with M elements scattered around inside of it, you're asked to move the least number of elements such that each cell in the grid have at most one element and all the elements are arranged in a way such that they form a rectangle

Solution:

First: what are the dimensions of said rectangle?

We can see that they are the divisors of M which are at most pairs, don't forget swapping width and hight

Second: which elements to move?

If we were to assume that our rectangle will occupy some arbitrary rectangle inside the grid, then the number of moves needed to rearrange the elements such that they would occupy that area is equal to E where E is number of empty squares in the rectangle

Third: which rectangle to pick?

The constrains are good enough for us to brute force all of them

We will do partial sums over 2D array of elements where grid[x][y] contains sum of empty squares in the rectangle designated by (1, 1)&(x, y)

With partial sums we can find number of empty squares anywhere in O(1) time

We have about rectangles, let's try every possible top-left point for each of them, no more than N² points in worst case

So our solution will run in time

First lets change the statement, you are given the dimension (x,y) of the required rectangle (x * y = M). To solve this problem you can put the upper left corner of the rectangle in every cell of the given matrix and check how many cubes are inside of it. Suppose there are C cubes, then obviously the answer is M - C for this rectangle. Be careful with towers of cubes.

Having solved this problem, you can try all possible rectangles with dimensions (x,y) such that x * y = M and keep the one that requires the least amount of moves.