Ninja and the Storyteller

Easy
0/40
Average time to solve is 15m
38 upvotes
Asked in companies
OlaAdobeSamsung

Problem statement

Ninja is an avid story lover. Today, he decides to go to the famous Storyteller of Ninjaland to listen to new stories. The Storyteller takes 'Y' coins to tell one story. The Storyteller has also put on a special offer for Ninja that for every 'X' story that the Storyteller tells to Ninja, the Storyteller will tell one story to Ninja free of cost, i.e., without taking any extra coins. Ninja currently has 'Z' coins with himself. He wants to know how many stories the Storyteller will tell him if he goes to the Storyteller with 'Z' coins.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first and the only line of each test case contains three space-separated integers,'X', 'Y' and 'Z', denoting the number of stories to get one free story, the cost of one story, and the number of coins that Ninja has respectively.
Output Format: 
For each test case, print a single line containing a single integer denoting the number of stories that the Storyteller will tell to Ninja.

The output of each test case will be printed in a separate line.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10 ^ 4
2 <= X <= 10 ^ 9
1 <= Y , Z <= 10 ^ 9

Where 'T' denotes the number of test cases, 'X' denotes the number of stories that Ninja needs to listen to get one free story, 'Y' denotes the number of coins the Storyteller takes to tell one story, and 'Z'  denotes the number of coins that Ninja has.

Time Limit: 1 sec.
Sample Input 1:
2
2 2 4
3 3 3
Sample Output 1:
3
1
Explanation for Sample Input 1:
For the first test case :  
The ninja will use the 4 coins that he has to listen to 2 stories. After listening to the two stories, the Storyteller will tell Ninja a free story. Hence, the answer is 3 in this case.

For the second test case : 
The ninja will give 3 coins to the Storyteller to listen to one story. Hence, the answer is 1 in this case.
Sample Input 2:
2
2 1 4
2 3 2
Sample Output 2:
7
0
Hint

Exhaust all the coins first, then listen to as many free stories as possible.

Approaches (1)
Optimized Approach

The idea is to first listen to all the paid storíes first, then listen to as many free stories as possible. Finding the number of paid stories is easy as the number of paid stories will always be floor(Z/Y) as Ninja needs exactly Y coins to listen to one story, and he  has Z coins with him. To know the number of free stories that Ninja will listen to, we will store a count of the stories whose corresponding free stories have not been claimed by Ninja. Initially, the count of such stories will be equal to the number of paid stories (floor(Y/Z)) itself as Ninja has listened to only paid stories till now. After getting the count Ninja will use them to claim their corresponding free stories which can be expressed as paidStories/X, and then we will do the same with the remaining stories, i.e, the new stories we have listened to (paidStories/X) and the stories whose corresponding free stories were not claimed in the last iteration (paidStories%X). The sum of the two values paidStories/X and paidStories%X will be used as the new value of paidStories for the next iteration. Our final answer will be the sum of the total paid stories and the total free stories.

 

Steps:

  1. Let paidStories be a variable that stores the number of paid stories. Initialize it as Z / Y. 
  2. Let freeStories be a variable that stores the count of free stories. Initialize it as 0.
  3. Define two variables storyCount to store the current count of stories whose free stories we have not claimed till now. Initialize it as paidStories
  4. While storyCount is greater than or equal X, then
    • Let the number newStories store the stories that we will listen to in the current iteration. Initialize it as storyCount/X.
    • Add newStories to freeStories. 
    • Let the number storiesLeft store the count of stories whose free stories were not claimed. Initialize it as storyCount%X. We will be using these stories in the next iteration to get free stories.
    • Update storyCount to the sum of newStories and storiesLeft, as this is the count of stories, whose corresponding free stories have not been claimed till now. 
  5. Return the final answer, i.e., the sum of paidStories and freeStories.
Time Complexity

O(log(Z / Y)), where Y is the cost of one story, and Z is the number of coins that Ninja initially has.

 

In each iteration of the while loop, we are diving the storyCount variable by X, and the storyCount variable is initially Z / Y. So, the total number of iterations will be log(Z/Y) and the base of the logarithm will be X.  Hence, the overall Time Complexity is O(log(Z / Y)).

Space Complexity

O(1).

 

We are using only constant extra space. Hence, the overall Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Ninja and the Storyteller
Full screen
Console