Welcome to the Algorithmic Toolbox course at Coursera! This file
                 contains the statements of 32 programming challenges.
                 Practice writing efficient and reliable code.  The programming chal-
                 lenges represent the most important feature of this course: we believe that
                 implementing an algorithm is a crucial computer science skill. You can
                 learn more about our teaching philosophy here. You will be practicing
                 writing efficient and reliable code for a multitude of algorithmic problems
                 using any of 12 programming languages: C++, Java, Python, C, C#, Go,
                 Haskell, JavaScript, Kotlin, Ruby, Rust, Scala.
                 Additional useful resources.   You may download all slides and video
                 recordings from this course here.
                 Prepare for you next coding interview.    Manystudents use our ªAlgo-
                 rithmic Toolboxº MOOCtopreparefortheirnextcodinginterview. Our
                 interactive textbook ªAce Your Next Coding Interview by Learning Al-
                 gorithms through Programming and Puzzle Solvingº prepares you for
                 a coding interview by covering all programming challenges and puzzles
                 in ªAlgorithmic Toolboxº. It further extends them by describing many chal-
                 lenges that you are likely to encounter on your next interview. The book
                 also discusses good programming practices that will help you to become
                 a better programmer and illustrates their use by providing Python solu-
                 tionsforallproblemsintheªAlgorithmicToolboxº. ItalsohasaTeaching
                 Assistant who responds to your comments to answer whatever questions
                 youmayhaveaboutalgorithms.
                 Contents
                    1 ProgrammingChallenges                                                              7
                        1.1   SumofTwoDigits . . . . . . . . . . . . . . . . . . . . . . . .             8
                              1.1.1    Solutions in Various Programming Languages . . . .                9
                              1.1.2    Submitting to the Grading System at Coursera . . .               11
                        1.2   MaximumPairwiseProduct . . . . . . . . . . . . . . . . . .                12
                              1.2.1    NaiveAlgorithm. . . . . . . . . . . . . . . . . . . . .          13
                              1.2.2    Fast Algorithm . . . . . . . . . . . . . . . . . . . . . .       17
                              1.2.3    Testing and Debugging . . . . . . . . . . . . . . . . .          18
                              1.2.4    CanYouTellMeWhatErrorHaveIMade?. . . . . .                       20
                              1.2.5    Stress Testing    . . . . . . . . . . . . . . . . . . . . . .    20
                              1.2.6    EvenFasterAlgorithm . . . . . . . . . . . . . . . . .            25
                              1.2.7    AMoreCompactAlgorithm . . . . . . . . . . . . . .                26
                        1.3   Solving a Programming Challenge in Five Easy Steps . . . .                26
                              1.3.1    ReadingProblemStatement . . . . . . . . . . . . . .              26
                              1.3.2    Designing an Algorithm . . . . . . . . . . . . . . . .           26
                              1.3.3    ImplementinganAlgorithm . . . . . . . . . . . . . .              27
                              1.3.4    Testing and Debugging . . . . . . . . . . . . . . . . .          27
                              1.3.5    Submitting to the Grading System . . . . . . . . . .             28
                    2 AlgorithmicWarmUp                                                                 31
                        2.1   ProgrammingChallenges . . . . . . . . . . . . . . . . . . . .             33
                              2.1.1    Fibonacci Number . . . . . . . . . . . . . . . . . . . .         33
                              2.1.2    Last Digit of Fibonacci Number . . . . . . . . . . . .           35
                              2.1.3    HugeFibonacciNumber . . . . . . . . . . . . . . . .              37
                              2.1.4    Last Digit of the Sum of Fibonacci Numbers . . . . .             39
                              2.1.5    Last Digit of the Partial Sum of Fibonacci Numbers .             40
                              2.1.6    Last Digit of the Sum of Squares of Fibonacci Numbers 41
                              2.1.7    Greatest CommonDivisor . . . . . . . . . . . . . . .             43
                              2.1.8    Least CommonMultiple . . . . . . . . . . . . . . . .             44
                        2.2   SummaryofAlgorithmicIdeas . . . . . . . . . . . . . . . . .               45
                        2.3   Interview Questions . . . . . . . . . . . . . . . . . . . . . . .         45
                              2.3.1    Josephus . . . . . . . . . . . . . . . . . . . . . . . . .       46
                              2.3.2    RangeSumQueries . . . . . . . . . . . . . . . . . . .            46
                             4                                                                   CONTENTS
                             3 GreedyAlgorithms                                                             47
                                3.1   TheMainIdea . . . . . . . . . . . . . . . . . . . . . . . . . .       50
                                      3.1.1   Examples . . . . . . . . . . . . . . . . . . . . . . . . .    50
                                      3.1.2   Proving Correctness of Greedy Algorithms          . . . . .   51
                                      3.1.3   Implementation . . . . . . . . . . . . . . . . . . . . .      52
                                3.2   ProgrammingChallenges . . . . . . . . . . . . . . . . . . . .         53
                                      3.2.1   MoneyChange. . . . . . . . . . . . . . . . . . . . . .        53
                                      3.2.2   MaximumValueoftheLoot . . . . . . . . . . . . . .             54
                                      3.2.3   CarFueling . . . . . . . . . . . . . . . . . . . . . . .      56
                                      3.2.4   MaximumAdvertisementRevenue . . . . . . . . . .               58
                                      3.2.5   Collecting Signatures . . . . . . . . . . . . . . . . . .     60
                                      3.2.6   MaximumNumberofPrizes . . . . . . . . . . . . . .             62
                                      3.2.7   MaximumSalary . . . . . . . . . . . . . . . . . . . .         64
                                3.3   Interview Questions . . . . . . . . . . . . . . . . . . . . . . .     66
                                      3.3.1   Job Scheduling . . . . . . . . . . . . . . . . . . . . . .    67
                                      3.3.2   MiceandaFox . . . . . . . . . . . . . . . . . . . . .         68
                                      3.3.3   Party Planning at Work . . . . . . . . . . . . . . . . .      69
                                      3.3.4   CookingaDinner . . . . . . . . . . . . . . . . . . . .        70
                                      3.3.5   GraphColoring . . . . . . . . . . . . . . . . . . . . .       70
                                      3.3.6   ConnectRopeswithMinimalCost . . . . . . . . . .               71
                                      3.3.7   BulbSwitching . . . . . . . . . . . . . . . . . . . . .       72
                                      3.3.8   Friends Seat Together . . . . . . . . . . . . . . . . . .     73
                                      3.3.9   MinimumUnchangeableAmount . . . . . . . . . . .               74
                             4 Divide-and-Conquer                                                           75
                                4.1   TheMainIdea . . . . . . . . . . . . . . . . . . . . . . . . . .       77
                                      4.1.1   GuessaNumber . . . . . . . . . . . . . . . . . . . . .        77
                                      4.1.2   Searching Sorted Data . . . . . . . . . . . . . . . . .       81
                                      4.1.3   Finding a White-Black Pair . . . . . . . . . . . . . . .      83
                                      4.1.4   Finding a Peak . . . . . . . . . . . . . . . . . . . . . .    85
                                      4.1.5   Multiplying Integers . . . . . . . . . . . . . . . . . .      86
                                      4.1.6   TheMasterTheorem . . . . . . . . . . . . . . . . . .          90
                                4.2   ProgrammingChallenges . . . . . . . . . . . . . . . . . . . .         97
                                      4.2.1   Binary Search . . . . . . . . . . . . . . . . . . . . . .     97
                                      4.2.2   Binary Search with Duplicates . . . . . . . . . . . . . 100
                                      4.2.3   Majority Element . . . . . . . . . . . . . . . . . . . . 102
                                      4.2.4   Speeding-upRandomizedQuickSort . . . . . . . . . 103
                                      4.2.5   NumberofInversions . . . . . . . . . . . . . . . . . . 105