PROBLEM LINK:
Contest
Practice
Setter: Priyanshu Vats
DIFFICULTY:
Easy
PROBLEM:
Problem setters are busy with their PS these days and have a pending report submission tonight. For setters to not lose marks and get ‘A’ in PS, they have asked you to solve this problem for them.
They have N special cakes from D-Mess, each of same size X. i-th of them is divided into i equal pieces. Size of each piece is rounded down to integer so that it can be processed easily, though it will generate some waste cake. One piece as a sample is taken from each special cake for testing purpose. Find the sum of sizes of all sample pieces. (These are actually reserved pieces in mess :P)
X, N are given.
EXPLANATION:
There are N cakes and one sample piece is taken from each cake. Therefore, there will be N sample pieces. Also, the size of i-th piece will be x / i (i-th cake is divided into i pieces).
So, answer will be the sum : x / 1 + x /2 + x / 3 .... + x / N (Integer division).
Brute force method: Running a for-loop from 1 to N will give TLE as N <= 10^9.
Better approach: For a better time complexity, we can do the following:
To start with let N = x because for all N > x, sizes further x-th cake will be 0.
We can find the sum into 2 parts : x / 1 to x / \sqrt x and x / \sqrt x to x / x.
First part can be done by simply using a for-loop from 1 to \sqrt x. For part 2, we will calculate its value in reverse order i.e. x / x to x / \sqrt x.
So, from x / x to what value will the result be equal to 1?
It would be upto x / (x / 2).
Therefore, from x / (x / 1) to x / (x / 2) result will be 1 (notice that we covered x / 2 operations from brute force method in 1 operation),
from x / (x / 2) to x / (x / 3) the result will be 2, and so on…
We continue this reverse part upto x / (x / \sqrt x) as x / (x / \sqrt x ) = x / \sqrt x. There will be some edge cases where x is a perfect square, so we will need to add/subtract to adjust our calculation.
Now, since we have calculated the sum x / 1 to x / x. We can similarly calculate the sum x / x to x / (n + 1) separately(as we did in part 2) and subtract it from previously found sum.
TIME COMPLEXITY:
In both parts, we are traversing upon \sqrt x terms at max. So, the overall time complexity will be O(min(N, \sqrt x))
SOLUTION:
Author’s Solution : PS lite - solution
Feel free to Share your approach, if you want to. Suggestions are welcomed as always had been.