Coding Test Set 6
1. In the city of Memo-Ville, there lived a record-keeper named Dyna. Dyna noticed that the village sprite,
Facto, was getting exhausted. Every time someone asked for the factorial of 10, Facto would calculate 10 X 9 X
8 ... all over again. If the next person asked for the factorial of 11, Facto would start from scratch!
Dyna decided to build a Great Ledger. "Instead of recalculating," Dyna said, "we will store every answer we
find in this book. If the King asks for 10!, we check the ledger. If it's there, we give it to him instantly. If he
then asks for 11!, we simply take our recorded 10! and multiply it by 11. No more wasted breath!"
The Strategy: Tabulation (Bottom-Up DP)
Dynamic Programming (DP) is all about solving sub-problems and storing their results to avoid redundant
work. For factorials, we fill a table (array) from the smallest value up to N.
1. The Base Case: We know 0! = 1 and 1! = 1. These are the first entries in our ledger.
2. The Build: For every number i from 2 to N, the value is i X Ledger[i-1].
3. The Instant Recall: Once the ledger is filled, any value can be accessed in O(1) time.
Test Cases Input (n) Expected Output Story Context
The Minimum 0 1 The ledger starts with the base truth.
Small Value 4 24 1×2×3×4.
Medium Value 10 3628800 Demonstrates the efficiency of building on 9!.
Negative -1 "Undefined..." Dyna refuses to record nonsense.
Large Value 20 2.4329E+18 Shows the ledger can handle massive weights.
2. In the land of Echo-Chamber, the residents had a strange habit: they would repeat their words many times. To
save space in the Royal Archives, the High Scribe invented a process called The Compression Whisper.
The rules were simple:
1. Look at a group of identical, consecutive numbers.
2. Keep the first instance of the number.
3. Count how many additional times it was repeated and write that count immediately after the number.
If a number stood alone, its "echo count" was simply 0.
The Strategy: The Scribe’s Tally
To transform the long sequence 5552229333344, the Scribe follows these steps:
The 5s: There are three 5s. Keep the first 5, count the remaining two. Result: 52.
The 2s: There are three 2s. Keep the first 2, count the remaining two. Result: 22.
The 9: There is only one 9. Keep the 9, count the remaining zero. Result: 90.
The 3s: There are four 3s. Keep the first 3, count the remaining three. Result: 33.
The 4s: There are two 4s. Keep the first 4, count the remaining one. Result: 41.
Test Cases Input Sequence Expected Output Story Context
Original 5552229333344 5222903341 The standard village message.
Single Digits 123 102030 Every number is unique; echo count is zero.
Massive 77777 74 One number repeated five times (1 original + 4
Repeat echoes).
Two Pairs 1122 1121 Two distinct groups of pairs.
Empty "" "" A moment of silence in the Echo-Chamber.
3. In the village of Unity, there lived a wise gatekeeper named Primus. His job was to decide which numbers
were "Primes"—the elite numbers that refuse to be broken down into smaller, equal groups.
One day, a massive number arrived at the gates. Primus was too old to check every possible divisor himself, so
he hired a team of Recursive Scouts.
The Strategy: The Scout's Investigation
When a number N arrives, the first Scout asks, "Can you be divided by 2?"
If the answer is Yes, the Scout shouts, "NOT A PRIME!" and the investigation ends.
If the answer is No, the Scout doesn't finish the job. Instead, he calls a slightly smaller Scout and says,
"I've checked 2. Now, you check if N can be divided by 3."
This continues, with each Scout checking one number and passing the task to the next. The investigation only
stops when:
1. A Divisor is Found: The number is proven composite.
2. The Safety Limit is Reached: A Scout reaches the square root of N (sqrt{N}) without finding any
divisors. He then reports back to the gate, "This number is a pure Prime!"
Test Cases Result Why? Story Outcome
1 FALSE 1 is neither prime nor composite. Primus turns it away immediately.
2 TRUE Smallest and only even prime. The Scouts find no divisors.
9 FALSE Divisible by 3. The second Scout catches it!
17 TRUE No divisors found up to sqrt(17) ≈ Passed by all Scouts.
4.12.
25 FALSE Divisible by 5. The Scouts find a divisor at 5.
4. In the mathematical province of Division-Dale, there lived a character named The Great Deconstructor. He
was a master of "Building Blocks." Whenever he encountered a large number, he didn't see one solid object; he
saw all the smaller whole numbers that could fit perfectly inside it without leaving a single piece of "Remainder
Dust."
One day, a giant number 24 fell from the sky. The villagers wanted to know all the different ways they could
divide this giant into equal, smaller teams. The Great Deconstructor stepped forward, took his "Sieve of Truth,"
and began testing every number from 1 up to the giant itself.
The Strategy: The Sieve of Truth
To find the factors, the Deconstructor follows a simple rule:
If the Giant Number (N) divided by a smaller number (i) has a remainder of 0, then i is a Factor.
1. Start at 1 (every number can be divided by 1).
2. Check every number up to N.
3. If N mod i == 0, add i to the list of building blocks.
Test Cases Input Expected Output Story Context
(n)
A Prime Giant 7 [1, 7] Only 1 and itself can fit; it's a "Prime" number.
A Small Square 4 [1, 2, 4] A perfect square has an odd number of blocks.
The Number 1 1 [1] The smallest building block.
A Larger Giant 12 [1, 2, 3, 4, 6, 12] Many different team combinations possible!
Invalid Input 0 "Please provide..." You can't deconstruct nothingness.
5. In the rhythmic city of Orbiton, the citizens lived in a giant circular housing complex known as The Array.
Each citizen lived in a numbered unit from 0 to n-1.
Every year, during the Great Shift, the City Governor would decree a rotation. If the decree was "d=2,"
everyone had to move two units to the left. The person in unit 0 would wrap around the city and end up in the
last few units.
The citizens hated moving their furniture multiple times, so the City Architect devised a clever three-step "Flip"
ritual that allowed everyone to reach their new homes with the least amount of effort.
The Strategy: The Triple Reversal
Instead of moving one by one (which is slow) or using a second city to store everyone (which is expensive), the
Architect used the Reversal Algorithm. To rotate an array by d elements to the left:
1. Reverse the first d elements: The group moving to the back flips their order.
2. Reverse the remaining n-d elements: The group staying in the front flips their order.
3. Reverse the whole array: By flipping everything together, everyone miraculously lands in their correct
new unit, facing the right way!
Test Cases Array (arr) Shift (d) Expected Story Context
Output
Standard [1, 2, 3, 4, 2 [3, 4, 5, 1, 2] A typical 2-unit city shift.
5]
Full Circle [1, 2, 3] 3 [1, 2, 3] Rotating by n means everyone stays home.
Over [1, 2] 5 [2, 1] 5 shifts (mod 2) = 1 actual shift.
Rotation
Single Unit [10] 100 [10] Only one person lives here; no move
possible.
Zero Shift [1, 2, 3, 4] 0 [1, 2, 3, 4] The Governor cancelled the Great Shift.