PROBLEM LINK:
Author: Devesh Jagwani
Editorialist: Devesh Jagwani
DIFFICULTY:
SIMPLE
PREREQUISITES:
None
PROBLEM:
The aim is to find the number of days to read ‘n’ pages given that we start by reading 1 page on the first day and read twice as many pages on a day than the previous day.
EXPLANATION:
This is a very simple problem, which can be solved in just one loop.
Given that the person reads twice as many pages on a day than he did a day before, we just need to double the number of pages he read a day before and then add these much number of pages to the total number of pages read by the person till the current day until the total number of pages becomes greater than or equal to ‘n’.
Since, the number of pages is doubled each day, the problem can be solved in a time complexity of O(logn).
We will start by assigning the number of pages read by the person on day one as 1 (according to the question). Then, we will assign the total number of pages read by the person till day one as 1.
Initially, the day count is 1.
Now, we can loop through until the total number of pages is less than ‘n’. Inside the loop, we will increament the day count by 1. Then, we will update the number of pages read by the person on the current day to twice the number of pages read on the previous day. Finally, we will add these much number of pages to the total number of pages read by the person till the current day.
We will get out of the loop when the total number of pages is either equal to ‘n’ or just greater than ‘n’.
Finally, the day count is our final answer.
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.