Minimum installment payment
A carrier sells handsets on an installment plan. principal_cents is the amount financed and the account is billed once a month for months statements. At each statement the carrier first adds interest of floor(balance * monthly_rate_bp / 10000) cents, where monthly_rate_bp is the monthly rate in basis points, and then takes the fixed installment. The plan is settled once the balance reaches zero or below, and the closing installment simply takes whatever is left. Return the smallest whole cent installment that settles the account within the given number of statements. Return 0 when nothing is financed, and -1 when a balance is owed but no statement is left to bill it against. An installment no larger than the first month of interest never settles anything, since the debt compounds on itself.
smallest_installment_cents(principal_cents: int, monthly_rate_bp: int, months: int) → int[120000,150,12]out11002[50000,0,4]out12500[100000,200,1]out102000State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
[120000,150,12]11002not run yetsample[50000,0,4]12500not run yetsample[100000,200,1]102000not run yetsample