PROBLEM LINK:
DIFFICULTY:
Cakewalk
PREREQUISITES:
Adhoc
PROBLEM:
The problem is related to apartment rents. The apartment has penalties for late payments. A thousand rupee payment is supposed to be made at the end of each month and a penalty of hundred rupee will be imposed for each delayed payment. The information about whether you paid for a month or not is given by an array a of size n, where a_i is a binary number where 1 denotes that the payment was made and 0 would mean it was not.
You have to find total remaining payment (including dues) that you should make.
EXPLANATION:
The important observation in the problem is that if you miss a payment for a particular month, then all the payments for upcoming months (including the current month) will also be delayed and will incur penalties.
So, let us find the first month x for which payment was not made (i.e. smallest x s.t. a_x = 0). All the months y \geq x, a penalty of 100 Rs will be paid. So, overall penalty paid will be (n - x + 1) * 100.
Other than this penalty the usual rent for missed months will have to be paid too. This will be total number of months for which rent is not paid multiplied by 1000 Rs (rent per month).
Pseudo Code
x = 1
for i = 1 to n:
if a[i] == 0:
x = i;
break;
unpaid_months = 0
for i = 1 to n:
if a[i] == 0:
unpaid_months += 1
total_dues = unpaid_months * 1000 + (n - x + 1) * 100
Time complexity of this solution is \mathcal{O}(n).