All Tracks>Basic Programming> Input/Output> Basics of Input/Output> Problem Try Out The Problem Here
how to solve this problem and what does this problem teach me?
Good question — this is a non-trivial problem that combines number theory and greedy reasoning. Let’s break it down step by step.
🔍 Problem Restated in My Words
We have two arrays:
-
a = [a1, a2, ..., an] -
b = [b1, b2, ..., bn]
Operation:
You can replace ai with ai - bi if ai ≥ bi.
You need to make all a[i] equal (same value) using the fewest steps.
If it’s impossible → output -1.
✨ Key Observations
-
Operation is like repeated subtraction (Euclidean Algorithm flavor):
-
ai = ai - bibehaves like reducing a number step by step by a fixed amount. -
Example: if
ai = 10, bi = 4, repeated operation gives sequence10 → 6 → 2.
Essentially:
Because subtracting multiples of
bikeeps remainder fixed. -
-
For all
a[i]to be equal:-
Their final values must be the same.
-
This means: all
ai % bimust equal the same target (otherwise impossible).
-
-
Checking feasibility:
-
If any
ai % biis different from the others, return-1.
-
-
Counting steps:
-
If feasible, steps for
ai=(ai - target) / bi. -
Total steps = sum of all steps for all
i.
-
✅ Solution Strategy
-
Compute
rems = [ai % bi for each i]. -
If all remainders are not equal → return
-1. -
Pick this common remainder
target. -
Compute steps:
-
Return total steps.
🔎 Walkthrough with Example
Example 1:
-
Remainders:
[5 % 4 = 1, 64 % 3 = 1]✅ equal. -
Target = 1
-
Steps:
(5-1)/4 = 1, (64-1)/3 = 21→ total = 22
But sample output says -1. Why?
Because second ai = 64 cannot reduce to 1 without first hitting negative values?
Let’s check:
64 → 61 → 58 → ... → 1. Works fine.
So here maybe sample assumes remainders must match AND the reduced values must match exactly. If a[i] < target case occurs → impossible. That’s why careful checking is needed.
Example 2:
-
Remainders:
[1, 1, 0, 2, 0]→ not all same. ❌
But solution gives8. Meaning: you can adjust differently and still converge.
So actually, the insight is:
-
You need to check if there exists some final value F that all
aican reach via allowed subtractions. -
That’s equivalent to requiring that
ai - Fis divisible bybi.
Thus:
-
Choose one
a[j]as candidate final valueF. -
Check if
(ai - F) % bi == 0for alli. -
Minimize steps over all possible candidates.
📘 What This Problem Teaches You
-
Modular arithmetic reasoning: You learned that operations like subtracting multiples of
bpreserve the modulo class. -
Feasibility check: It’s not enough to just brute force; you need to reason about remainders and divisibility.
-
Optimization mindset: Instead of simulating step by step, you derive a formula for the steps.
-
Greedy vs Number Theory: This blends greedy subtraction logic with number theory (remainder classes).
👉 In summary:
-
It teaches you to translate repeated subtraction into modular constraints.
-
It also teaches you how to check feasibility (common final value exists).
-
It trains you to optimize without brute force.
Do you want me to write a step-by-step pseudocode (and then Python solution) that implements the exact logic?
yeah, sure
Perfect 👍 Let’s carefully build this up into pseudocode and then a clean Python solution.
🔎 Step-by-Step Pseudocode
✅ Python Implementation
💡 Explanation of Approach
-
The operation preserves
ai mod bi. -
Therefore, each
aican only become values of the formai - k*bi. -
To make all
a’s equal to the same final valueF, we need:-
F ≤ ai -
(ai - F) % bi == 0for alli
-
-
By trying every
aias a candidateF, we ensure we don’t miss any possible final value. -
Then, for each candidate, compute steps needed and choose the minimum.
Would you like me to also show the step-by-step reduction process for one of the sample cases (like [5,7,10,5,15] with [2,2,1,3,5]) so you can visualize how the 8 steps happen?

















