Amazon Online Assessment 2021 (OA) - Coin Sequence
Think about a special book for coin collectors. This book has a coin on each page, and the coin could be showing heads (marked as "H") or tails (marked as "T"). Some people think a book looks great if all the coins showing heads come before the coins showing tails. In other words, all the "H" coins are at the front and all the "T" coins are at the end, so it's like "HHH....TTT."
Now, picture someone who enjoys collecting and arranging coins. This person sticks n coins onto n pages in the book. After that, they want to rearrange them so the book looks nice, with all the heads at the front and the tails at the back. From how the coins are initially placed, we need to find out how many coins need to be turned over (flipped) to get the book looking nice.
Remember, a book that only has coins showing heads, or only has coins showing tails, is still considered to look nice. So no need to worry if all the coins are the same side up!
Example
- coins =
HHTHTT: Flip the fourth coin to obtain the beautiful sequence "HHTTTT". The answer is 1. Note that this is the minimum number of coins that must be flipped to make the coin sequence beautiful.