Silver 2020 Jan Loan Repayment with Binomial Theorem

Problems and Contests
#1

I n the problem Loan Repayment, I have found potentially a faster way to check if an integer x is viable (in theoretical O(1) time) thus speeding up the entire solution from O(sqrt(n) * log n) to O(log n).

However, I couldn’t quite get my solution to work and was wondering if someone on here would be willing to help out or let me know if this is a dead end.

My method is described here: https://admiring-poitras-f4ec43.netlify.app/loan.

1 Like
#2

Although this seems promising, in my eyes it probably is a dead end- if there was an O(1) method to check, the official solution probably would have mentioned it.

#3

Well, this isn’t great reasoning - perhaps we just didn’t think about it for very long. :stuck_out_tongue: Anyways, I don’t know how to fix it.

#4

Lol thanks for having a look anyways :slight_smile:

#5

I tried a similar solution, but it is simply not possible because of how floor functions and max are used.