PROBLEM LINKS:
DIFFICULTY:
Simple
EXPLAINATION
Problem [Toggle Candles] : After performing operation on 1 to 10^18 candles:
for i = 1 to 10^18 do :
Toggle the all candles which are multiple of i.
The answer is all candles no (i) which are perfect square will be turned on.
Mathematical reason is simple: only perfect square have odd number of divisors.
For eg . i = 16 : total 5 distinct divisors are
1 , 16
2 , 8
and 4
So initially candle is turned off and will be toggled odd no of times [ in this eg 5 times] , So it
will be turned on at the end.
So answer for each query is no of perfect squares in the range [L R].
ans = (int)sqrt(R)-(int)sqrt(L);
if(R is perfect square)ans = ans +1;
Key Point : c++ , java library SQRT function give wrong value at high range boundary case data. So
to get correct value of (int)sqrt(R) we can use binary search follows :
int tests = readINT();
for(int t=1;t<=tests;t++){
long L = readLong();
long R = readLong();
long left = sqrtLower(L);
long right = sqrtLower(R);
ans = right-left;
if(left*left==L) ans=ans + 1; //checking left perfect square.
out.write(“”+ans+“\n”);
}
public static long sqrtLower(long n)throws Exception{
long l = 1; long r = 2000000000L;
long mid=0;
while(l<=r){
mid = l + (r-l)/2;
if(mid*mid < n){
l = mid+1;
}else if(mid*mid==n){
return mid ;
}else{
r = mid-1;
}
}
return l-1;
}
Time Complexity : Big O(T*logN) where N = R-L = 10^18
Reference Solution