Tricolor Arrangement — Puzzle for Interview rounds

Question :

A rectangular board with three rows and n columns is filled with 3n counters, of which n are red, n are white, and n are blue. The object is to rearrange the counters to have counters of each of the three different colors in every column. The only operation allowed is to swap counters in the same row. Design an algorithm to accomplish this task or prove that such an algorithm does not exist.

Solution :

If n = 1, the problem is already solved: all three counters in the only column are of the three different colors. If n > 1, we will show that the counters can be rearranged so that the three counters in the first column are of the three different colors; repeating such a rearrangement for the boards of decreasing sizes will solve the problem. Consider the counters in the first column. There are three possibilities: (i) all three of them are of the different colors, (ii) exactly two are of the same color, and (iii) all of them are of the same color.

In case (i), nothing obviously needs to be done with the counters in the first column.

Consider case (ii); we assume without loss of generality that the two counters of the same color are, say, red and they are in the first two rows, whereas the counter in the first column and the third row is, say, white (see the diagram below). Since there are n blue counters on the board and no more than n − 1 of them can be in the third row, at least one of them must be in the first two rows. Hence the algorithm in question can scan the first two rows starting with column 2 until a blue counter is encountered; after a blue counter is found, it should be swapped with the red counter in the first column.

Finally, consider case (iii). We assume, without loss of generality, that the three counters in the first column are red. Since each of the three rows must then contain at least one counter of the color other than red, we can scan, say, row 3 to find such a counter and swap it with the counter in the first column to get the situation of case (ii).

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.

--

--

--

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Download In @!PDF Introduction to Earthquake Engineering Read ^book %ePub

coroutine

Alibaba Cloud Best Practice for CDN: A Comprehensive Analysis on Industry Applications

AVA gecko node on raspberry pi 3B with ubuntu server 18.04 64bit, without monitor and keyboard.

Factory Design Pattern

How to build OpenCV with Cuda and cuDNN support in Windows

A free front-end developer setup

Why GitHub Copilot Will Not Change Programming

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Placewit

Placewit

Upskilling students for tech placements!

More from Medium

Class Quiz

Graph Algorithms

“Delete and Earn” problem using Dynamic Programming

Leetcode 290. Word Pattern