3 ms·
A puzzle I made up that might be good for technical interviews: "slider puzzle with a twist"
You are given an array of n x n integers.
The goal is to end up with an array in which all entries are equal.
Four kinds of moves are allowed:
(1) rotate a row
(2) rotate a column
(3) add 1 to all entries in a row
(4) add 1 to all entries in a column
Show the goal is achievable if and only if the sum of the numbers
in the initial configuration is congruent to 0 mod n.
- amalcon 19y agoIt's actually pretty easy -- you can only change the total value of the board by n at a time (takes care of the "only if" part, because the "all equal" state also requires the sum mod n to = 0). You can increase a single cell by n in exchange for increasing all cells (including that one) by 1 (by hitting the column it's in, then the row it's in, then rotating the column, repeat). You can spread the n part of that "increase" out over any number of cells you like, in any (whole) allocation you like, because it's clearly easy to put whatever cells you like in one column. So that lets you equalize everything as long as you move the deltas in clumps of n, which satisfies the "if" part.
- amichail 19y agoCould you give an example to illustrate your method?