PROBLEM LINKS:
Author: Animesh Fatehpuria
Testers: Rajat De Sumit Shyamsukha
Editorialist: Animesh Fatehpuria
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Math, Factorization.
PROBLEM:
A bank has N vaults numbered 1 to N where the ith vault contains i rupees. Initially all vaults are closed.
N guards enter the bank . The ith guard reverses the state(open or closed) of every ith vault.
Calculate the total sum of money which can be robbed after all the guards leave. Money can only be stolen from OPEN VAULTS.
EXPLANATION:
How To Get 30 Points:-
Since the ith guard reverses the state of EVERY ith vault and each vault is initially closed , There must be an ODD number of state reversals (open and close) for that vault to remain open at the end of the security check by all the guards.
The important observation is that the state reversals can be thought of as factors of a number.
If a VAULT X has an odd number of factors , that vault X will remain open at the end of the security check.
The only numbers which satisfy this property of having an odd number of factors are PERFECT SQUARES.
To get 30 points , one must just check whether a number is a perfect square or not .
If it is, add the number to the total sum.
This O(N) algorithm is acceptable for 30 points as N<=1000.
How To Get 70/100 Points :-
For 70 Points The complexity should be O(sqrt(N)) as N<=10^12 . Hence O(N) will be unacceptable.
To do this , we just have to square root the given number N and round it down to the nearest Integer(Using Math.floor is also feasible). Then, we simply have to iterate from 1 to sqrt(N) and add the squares of each number to the total sum.
For 100 Points , The complexity should be O(1). We simply have to use the formula :
*Sum of Squares of Natural Numbers = x(x+1)*(2x+1)/6
Here x=(long)Math.floor(sqrt(N))**