# Sherlock and Squares

# Sherlock and Squares

DollarAkshay + 36 comments Code Golf solution

`main(a,b){scanf("%d");while(scanf("%d%d",&a,&b)>0)printf("%d\n",(int)(floor(sqrt(b))-ceil(sqrt(a))+1));}`

1 Line Code :P

alexndreazevedo + 1 comment Very nice! Haven't the constraints tests, but http://goo.gl/dHHG60. =D

Singhalr31 + 1 comment wanna ask just one question how you guys think like that??? i mean i just spent more than an hour thinking a formula for this problem but ended up seeing solution for it here in problem discussion..!! how to start think in this way?? :(

akiam595 + 0 comments practice

mostafa_asg + 3 comments How you find this formula? why this formula is correct?

alexndreazevedo + 4 comments Is simple! Count all integers found between the square roots given.

StephnR + 3 comments Can someone explain this? I do not understand how this makes sense

Arius + 14 comments See if the square root of starting number is say 5.6 and ending number is lets say 8.1 then in between you have 5.7 ,5.8, 5.9, 6, 6.1 and so on till 8.1. But we know that square root of only perfect square will be an integer, so the number of integers between 8.1 and 5.6 will tell us exactly how many perfect squares are there between corresponding numbers.

readman + 0 comments Perfect explaination

Icarus_XXII + 4 comments Still makes no sense to me... :(

suyashsngh + 2 comments Find the sqrt of ends and subtract it u will get the number of perfect squares in between them

svijay1991 + 2 comments Then it will fail for the following input 4 4 the expected output is 1 and as per your solution Sqrt 4=2 and then 2-2=0

arfouchem + 1 comment do not forget that 2-2 + 1 wich equal to 1 and it still right

vi123 + 1 comment [deleted]cesarjom + 4 comments that's wrong... case A=B only returns 0 when A is not a square integer. When A is a square integer and A=B, then you return 1. The following code (as others have suggested) does indeed satisfy the "A=B case" if you understand Floor and Ceiling functions:

`int count = (int)Math.Floor(Math.Sqrt(b)) - (int)Math.Ceiling(Math.Sqrt(a)) + 1;`

boleke + 0 comments true

vvbhandare + 1 comment Perfect One. Please tell me how did you find the formula?

caccaacccaaa + 0 comments Perpect !!

rahulmurugan + 0 comments perfect

itsmeguptapankaj + 0 comments right

borse1012 + 1 comment Right, In that case you need check condition like if square root of start number is whole number then you have to add 1, else just print difference.

piyusman + 1 comment int count = (int)(Math.floor(Math.sqrt(b))- Math.ceil(Math.sqrt(a)))+1; Basically Its a math formula to find number of squares in a given range. We do the floor of larger number sqrt and ceiling of smaller number sqrt. Reason being we need to find number of integers between the sqrt of those numbers.

spartacus_arena + 0 comments Thats why I love maths.

saichakri + 0 comments test cases are failing

vi123 + 14 comments Suppose you want to calculate all the square integers between 3 and 14. calculate the square roots of the end points..that will be around 1.73 and 3.74. Now the integers between 1.73 and 3.74 are 2 and 3 which is what we want. To get this we use the ceil function on 1.73 which becomes 2 and we use the floor function on 3.74 which becomes 3. Their difference is 1. We add 1 to the difference because we rounded off 1.73 to 2 and since 2 is an integer we need to consider it also. Hope this helps

Icarus_XXII + 1 comment This is some strange math.

Alexvhr + 13 comments That's not "strange math", this is basic math. You need to understand the concept of inverse function (https://www.mathsisfun.com/sets/function-inverse.html).

For our case, look at the graph of y = x

^{2}. For each point y of the graph, there is an x, square of which will give the graph value (y). This x can be found with inverse function, sqrt(x).For the interval [a,b] for y, all x which give the y point in [a,b] lay in the [sqrt(a), sqrt(b)] interval. This follows from the definitions of function and inverse function.

So, to count all

*whole*y from [a,b], we need just to count all whole x from [ceil(sqrt(a)), floor(sqrt(b))]. (ceil(x) gives closest high integer for x, floor(x) gives closest lower integer for x - see*Topics*tab). For interval [m, n] (m,n are whole, including endpoints m, n), the number of integers in it is (n - m) + 1. This gives us the solution.

We can generalise this: all whole numbers of f(x) in [a,b] can be counted as:

*floor(f*^{-1}(b)) - ceil(f^{-1}(a)) + 1Now Sherlok can easily found the number of cubes in [a,b], number of degrees of 2 in [a,b], etc, provided he has proper inverse function :).

isacB + 0 comments Very nice explanation

Maverick_911 + 3 comments I am able to understand your logic. But instead of using the ceil and floor functions I tried saving the sqrt values in int so that the values after decimal is neglected. For example, for [3,10] sqrt(3) gives 1 and sqrt(10) gives 3 when stored in int. Their difference gives the correct answer 2. But it doesn't work in some cases. I am not able to understand what is difference in my logic and the ceil-floor logic. P.S. I included a case if both numbers are equal. Ex [4,4] so it is certainly not an issue.

f2014074 + 1 comment [deleted]lawless_war1ock + 1 comment only first 2 cases and the last 2 cases run others don't

abhiroyg + 0 comments It's because if you are storing in int you are internally applying floor. Here ceil is also needed.

sakshamgoyalswm + 0 comments your result will be one less than the actual result, it should be because in your case you have miscounted the case when the a (while integers are from (a,b)) is itself a square number

Sumiibi + 0 comments Nicely Explained. Thanks.

irkjsdb + 0 comments Very helpful

greenhorn101 + 0 comments Thanks for this explanation! That was very helpful.

cdr95 + 0 comments [deleted]abhishekramkumar + 0 comments Great explanation Alex

spartacus_arena + 0 comments Is this necessary to go too deep to understand these concept?

thong1411998 + 0 comments Very great explanation , Thank you very much

asadjivani + 0 comments Amazing observation. .Thanks alot.

kharatpriyank + 0 comments Amazing explanation!

Mrsolodolo + 0 comments I think inverse function should be sqrt(y) ??

b_s_apsara_july + 0 comments Finally understood how this formula came...Very nice explanantion....Thanks

code_school_9 + 0 comments [deleted]DHARININEHRU + 0 comments nice explanation. Thanks a lot

ashishgoyanka + 0 comments Great Explaination

hemanth_savasere + 0 comments nice and good explanation

alamb76 + 0 comments Used a similar formula, but I ended up with (using Java)

`(int)Math.floor(Math.sqrt(B)) - (int)Math.floor(Math.sqrt(A-1))`

It works on all the test cases, but I am wondering if this is mathematically the same thing. I rounded down on A instead.

desi_duuh + 0 comments As a person who doesn't prefer Math, THANK YOU!

eunha0174 + 0 comments Very thanks.. Math knowledge necessary to solve this problem.

kshuvo96 + 0 comments thank u well explain

kushagrapathak91 + 0 comments thank you very much it helped alot.

mukuldutt1234 + 0 comments lol thankYOU <3 (int)Math.floor(Math.sqrt(b))-(int)Math.ceil(Math.sqrt(a))+1;

syedjawadakhtar + 0 comments Amazingly explained!!! Thanks!!

neha86_arora + 0 comments Its interesting.. difficult at first and simple when understood..

codedas_dyanesh + 1 comment See, let us assume a number x inclusive in the range [a,b] Then,

a<=x<=b

if both a,b are positive apply square root across the equation

sqrt(a)<=sqrt(x)<=sqrt(b)

since we need perfect square os sqrt(x) should be an integer between the two number sqrt(a) and sqrt(b) Accordingly we apply floor and ceil

dont_know_me + 0 comments Thank you so much for explaining it simply.

kevinbrewer04 + 8 comments Let me try to give a better explanation.

We're given two numbers which represent the start and end of a sequence, for example:

`4, 16`

Our objective is to find how many numbers in the sequence

`4 5 6 7 ... 15 16`

are square integers.A square integer is a number whose square root is an integer.

If we take the square root of the start of our sequence, it allows us to determine the lower boundary of the square integers that could possibly occur in our sequence.

How do we know this? Let's walk through it step by step:

In our example (4, 16), the square root of 4 is 2.

2 is an integer, which means 4 is a square integer - the lowest square integer in our sequence. Our sequence starts at 4, after all. Anything lower would definitely be outside that range.

Let's pretend for a moment that our sequence starts at 5 instead of 4. The square root of 5 is 2.24. Since 2.24 is not an integer, we know that 5 is not a square integer. If we round down from 2.24, we get 2, which is the square root of 4. If our sequence starts at 5, it does NOT include 4. This is why we have to round up when we take the square root of our starting number.

Rounding up from 2.24, we get 3, which is the square root of 9. So that means for a sequence starting at 5, 9 is the lowest square integer that could possibly occur, if the sequence happens to go that high.

Next, let's look at the upper boundary. We get the upper boundary by taking the square root of the end of our sequence. For our original example (4, 16), if we take the square root of 16 we get 4. Since 4 is an integer, that means 16 is the highest possible square integer that could occur in our sequence. Again, our sequence ends at 16, so anything higher is definitely outside our range.

Ok, once more: let's pretend our sequence ends at 17. The square root of 17 is 4.12, so that tells us 17 is not a square integer. If we were to round up from 4.12 like we did with our starting number, that would give us 5, which is the square root of 25. We know our sequence ends at 17, so 25 is outside that range. This is why we have to round down when we take the square root of our ending number.

Rounding down from 4.12, we get 4, which is the square root of 16. That means for a sequence ending at 17, 16 is the highest square integer that could possibly occur, provided that our sequence starts low enough.

Putting it all together, we know the lowest possible square integer in our sequence is 4, and the highest possible square integer in our sequence is 16. The square roots of these boundaries are 2 and 4, respectively.

If we walk up in integer steps from the lowest square root to the highest, we get the sequence

`2 3 4`

. We know for sure that squaring each of these integers will result in a square integer, and we know each of these square integers will be within our range.So now all we have to do is calculate the length of our sequence of square roots, and that will give us the number of square integers that are within the range of our original sequence.

For our example, our sequence of square roots starts at 2 and ends at 4. We can approximate the length by taking the difference of the endpoints (

`4 - 2`

), which is 2. But this calculation leaves out the first number in the sequence, so we have to add 1 to get the true length.Congratulations, we did it!

`4 - 2 + 1 = 3`

, which is the length of the sequence`2 3 4`

, which are the square roots of the square integers`4 9 16`

, which are the three square integers in our original sequence`4 5 6 7 ... 15 16`

!osamaejaz1 + 0 comments thank you :)

cary_a_miller + 0 comments Ok, that was an excellent explanation. Thank you!

Divas0103 + 0 comments amazing .. its really so helpful.

tanjuljain + 0 comments Excellent explanation

kirubha_16p119 + 0 comments this was very useful thank you

smarsh + 0 comments Plain english and clear. Not something you see everyday here on Hacker Rank. Thank you!

manishmeshram51 + 1 comment thanks :)

reaped_juggler + 0 comments never a problem :) keep coding

menyus_szelei + 0 comments Best explanation! Thx

aayushARM + 0 comments Damn! Far better than iterations...

manasaedula11 + 0 comments wow simly superb,thanks for the explanation

justnotcoding + 0 comments You deserve a medal for this extremely simple explanation. Well done.

ajboss + 0 comments perfect! i went all the way through n got timeout

mchisty + 0 comments [deleted]pankaj_mittal372 + 0 comments thanks!

cyberajit + 0 comments Awesome! ... that helped! :)

josergc + 0 comments Thank you very much for the explanation!

saiteja_malladi + 0 comments Very nice one. Thank you...

sunil98meena + 0 comments how to see which no. is integer which is not??

aakankshashastr1 + 0 comments awesome!!

hetp111 + 0 comments Perfect...!

Alexvhr + 1 comment The proof follows from math definitions of function and inverse function. See my comment in this thread:

https://www.hackerrank.com/challenges/sherlock-and-squares/forum/comments/64077

reaped_juggler + 0 comments if you want perfect squares then the sqrt(n) will follow the property (floor(sqrt(n))-ceil(sqrt(n))==0 this means you need to count all integers in range(sqrt(a),sqrt(b)) :)

HarshaXSoaD + 4 comments I dont know wether this will increase significant amount of performance. but rather than performing checks on all the integers in between we can find the square root of first square number in given range and then increase it by one untill its square is not exceeding the given range.

So we can save number of iterrations, and checks we have to performe. guess it will reduce the number of iterrations atleast by 40%. Thanx...

sidmeister + 0 comments your method will run at atleast

`\Omega(n^{1/2})`

time. Which is way higher than this`\theta(1)`

timeAronTD + 1 comment He's not doing any iteration. He's just subtracting the lowest possible sqrt from the highest possible sqrt.

sidmeister + 1 comment "we can find the square root of first square number in given range and then

`increase it by one untill its square is not exceeding`

the given range."AronTD + 1 comment Yes, I know that. I was responding to Harsha, not you. We're in agreement. Hackerrank has this bogus commenting system that alerted you for some reason.

sidmeister + 0 comments Ah. My bad.

dannyv573 + 1 comment That was actually very helpful. I was able to convert that idea into this code.

`for(j=a[i]; j<b[i]; j++){ /* i<=t-1; */ c = sqrt(j); d = c*c; if(d==j){ s += 1; /* number of squares */ j = b[i]; } } while(d<=b[i]){ c++; d = c*c; if(d<=b[i]) s += 1; }`

I didn't use /* text */ in my code. It's just there for understanding.

eliodeb + 12 comments Had the same Idea. First tried just iterating through every number in the range but my solution was timing out except for the first 2 and last 2 cases. Then I just noticed that the closest squares (in low ranges) appear always after more than twice the previous perfect square added to the current position (e.g. square 1: 1 + 2*1 = 3, the next square is 4: 4+2*2 = 8, the next square is 9: 9+3*2 = 15, the next square is 16 and so on for 25). By doing this you skip a lot of useless numbers and the solution does't time out.

`int main() { int t; cin >> t; for(int a0 = 0; a0 < t; a0++){ int a; int b; int count = 0; cin >> a >> b; int range; for(range = a; range <=b; ++range){ int temp = sqrt(range); if(temp*temp == range) { count++; range += temp*2 ; } } cout<<count<<"\n"; } return 0;`

}

ranju73 + 0 comments great coding!

Epshita + 0 comments Nice coding!

uwaisulde + 0 comments Dude its awesome.great work

karananandkk + 1 comment `range += temp*2 ;`

why the above code is used ?

manojbabu115 + 1 comment for example 4 ;(range=range+temp*2) 4+2*2=8;up to 8 there will no perfect sqrts..5,6,7,8 are not perfect sqrts

avish_ai + 0 comments [deleted]

nandhini_r_20151 + 0 comments can you please explain it ...

positivedeist_07 + 1 comment After incrementing count, the range is incremented. And yet, when it goes into the loop again, range is incremented. Why the need for double increment?

positivedeist_07 + 0 comments My bad!! I found out it causes time out :/ So yeah, the double increment is necessary!

Striker437 + 0 comments superb logic

kickkick + 1 comment range += temp*2 ; can u explain this step;

manojbabu115 + 1 comment for example 4 ;(range=range+temp*2) 4+2*2=8;up to 8 there will no perfect sqrts..5,6,7,8 are not perfect sqrts

shivam_deep + 1 comment [deleted]nishantraj140211 + 1 comment if range is 9 then range=9+3*2 range=15 and there is no perfect square b/w 10 and 15

shivam_deep + 1 comment Thanks!

reaped_juggler + 0 comments welcome !

siddhartkothari1 + 0 comments I didn't realize that. Thanks for explanation.

aashishbuddy1234 + 0 comments nice observation..thanks for explaining!

cbhawana603 + 0 comments amazing

sayakhaldar640 + 0 comments Nice one brother!

maklaka + 1 comment That's what I had to do because iterating over the larger range of square integers was timing out in my C# solution. Switching it up took some edge case work I didn't want to do but it's working now >,>

bahugunayush + 2 comments range += temp*2 ;

Dude can you please explain !

mdazhar0m123 + 0 comments [deleted]mdazhar0m123 + 0 comments let range =4 so you will reach now to 8(4+2*4) nearest to another perfect square

Loydik + 0 comments I don't know how I did not think about this!! Came up with a complicated solution (relative to yours) instead :(

Kuriocity + 0 comments [deleted]

piyusman + 0 comments [deleted]alaniane + 3 comments Here is an inverse of the formula that may help someone understand why the square root formula works:

int squares(int a, int b) { int numOfSquares = 0; int x = 1; while(x*x < a)x++; while(x*x <= b){ numOfSquares++; x++; } return numOfSquares; }

christopher_g_c2 + 0 comments Without having seen your code, I came up with pretty much exactly the same solution. It took me 10 minutes to do as a few month ago, I had a simular but more complicated problem with cubes and negative numbers in range allowed. Performance wise, it is probably amongst best solution possible, as not worrying about sqrt and intermediate values that are not squares.

madhavarapurao71 + 0 comments Thank you .Great code !!

m_bagus_oka + 0 comments Brilliant.

3yakuya + 0 comments I was thinking exactly the other way round - results were awful. Thanks!

flawlessvoid + 0 comments This is beautiful. It doesn't just solve the problem; it understands the problem deeply.

iGbanam + 0 comments This is sublime!

lawless_war1ock + 0 comments isn't rounding of the(floor(sqrt(b))-ceil(sqrt(a))+1)); necesasary>?/?

alacret + 0 comments That ceil part is a minus (-) operation instead of a sum (+)

JonAmazon + 1 comment This code fails because it's not careful with the rounding of floats to integers. If sqrt(25) returns 5.0000000001 then the ceil() will return 6 and give a wrong result.

zac_c_petit + 0 comments This just means that the solution can fail if you manipulate

`float`

... using another type like`decimal`

should work fine.

evilcat + 0 comments [deleted]zac_c_petit + 2 comments This is illegible. I don't care how efficient the solution is if I can't read it.

Ayelis + 1 comment I'm with this guy. Plus, it's intellectually dishonest to call it "1 line of code" when there are semicolons involved. I demand a rewrite. If you can't write this in 1 line without semicolons, you can hardly call yourself a programmer. ;)

Juancho_Villa + 0 comments Where is your semicolon-less one line solution?

No it is not dishonest to call one line of code, one line of code. It is, as a matter of fact, very honest.

Juancho_Villa + 4 comments It is not illegible, and if you think it is illegible go in and change the code, that's the beauty of programming.

You should also change your views on code readability, code wasn't made to be read by humans, it was made to be read by computers, you have to remember that you aren't the most important piece of the puzzle.

jeokeefx + 0 comments that is the single most wrong thing i have read on the internet this week. wow. The single MOST important thing is code readability. Especially if you are working on a project with a group of people.

Bob_Roebling + 0 comments Except if you come back to this code at a later time (years) you have no idea what it does.

Programs were meant to be legible by people, code comments and whitespace are ignored by the compiler at build.

Regardless of if you write

print("Some line of text")

or

print( "Some line of text" )

the compiler won't care.

Also I've seen one liners take longer to finish than I have broken out code. Granted it was milliseconds, but in devland that's a long time, you start noticing the performance hit when all your methods take that long and you have hundreds of methods.

Also have to think of change.

You write a one liner to perform some task, leave no comments and make it hard to read. A year later your boss comes around and says hey found an issue in your code, line 5 error 4.

Well if line 5 has 10 things happening in one line, all you can hope for is that error 4 and it's not some random code generated by the compiler and its a well documented error code that means your Int didn't convert properly (maybe it is a nil value).

However, if it's line 5 error 4 and line 5 is a single task in 10 lines of code, you'll know exactly what's wrong with your code and you can immediately start testing with breakpoints to find out why it's broken.

bryant_hector + 0 comments Nope. Code

**is**meant to be read by humans. Computers don't understand code, they understand machine langauge. Even Assembler is meant for humans. It all gets compiled (ignoring interpretation cases as ratholing ...)!

darrenbkl + 2 comments google search engine could be written in one line by eliminating space and \n too

zac_c_petit + 1 comment That doesn't make it good code. Good code needs to solve the problem under conceivable conditions AND be written so that it can be understood by people unfamiliar with it! If conditions change and the code must be updated, a one-line solution is horrible to work with.

darrenbkl + 0 comments exactly

Ayelis + 0 comments Agreed. "1 line" + "2 semicolons" = "3 lines". No matter how you .slice() it.

madhan_coder + 0 comments I am not able to use sqrt here.

kamalraghav + 1 comment thanks mate, just cleared some chaff from your code

inline int squaresCount(int a, int b) {

`return a == b ? ((sqrt(a) - floor(sqrt(a))) > 0.0 ? 0 : 1) : (floor(sqrt(b)) - floor(sqrt(a)));`

}

kkamrul_hasan + 0 comments [deleted]

dbarkman + 0 comments Brilliant!

raphnguyen + 0 comments This solution is genius. Always awesome to find room for more optimization.

Kronodeus + 0 comments Frustratingly smart.

ashish1702 + 0 comments Thanks !

congtrang009 + 0 comments perfect!

amitkm9204 + 0 comments thank you for your logic.. your logic needs some implementation and it is as:

`cin>>a>>b; l=sqrt(a);h=sqrt(b); if(l!=h) { if(l*l!=a) cout<<h-l<<endl; else cout<<h-l+1<<endl; } else { if(l*l==a) cout<<h-l+1<<endl; else cout<<h-l<<endl;; }`

nhathuy13598 + 0 comments Your formular is great. Thank you

RodneyShag + 0 comments If you don't like 1 line solutions, here is a similar Java Solution that uses the same concept but is easier to read.

From my HackerRank solutions.

josergc + 0 comments Thank you very much for the trick!

sanyachaba26 + 0 comments test case #3 is working with this solution?

mahak1 + 0 comments what is the reason for adding 1?

16bit155 + 0 comments can you please tell me that why you have written +1 in the end?

Learner_V1 + 0 comments Awesome

vishwasjha17 + 0 comments my code without using lib function :?

int main() { int t; cin>>t; while(t--) { int a,b,l,s; cin>>a>>b; l=min(a,b); s=max(a,b); int j=0,k=0; for(int i=1;i*i<=s;i++,k++) if(i*i==l) k=k+1; for(int i=1;i*i<=l;i++,j++); cout<<k-j<<endl; } /* Enter your code here. Read input from STDIN. Print output to STDOUT */ return 0; }

mail2karthk07 + 2 comments Using Python 3..with Same Logic.

import math for _ in range(int(input())): a, b = list(map(int, input().split())) print(math.floor(math.sqrt(b)) - math.ceil(math.sqrt(a)) + 1)

coolharman123 + 1 comment can u explain the logic behind it?

ekostyuk + 0 comments

Mrsolodolo + 0 comments No to do list(map), map will return list only...

daiict_201712029 + 2 comments **JAVA O(1)**`Scanner sc = new Scanner(System.in); int t = sc.nextInt(); for(int i=0;i<t;i++) { int a = sc.nextInt(); int b = sc.nextInt(); System.out.println((int)(Math.floor(Math.sqrt(b))-Math.ceil(Math.sqrt(a))+1)); }`

bnisb + 0 comments It's amazing. thank you

krishbht15 + 0 comments The best logic

rajat_yadav + 0 comments simple algorithm is 1) find the first square in the list suppose k 2) find square root of that square suppose m 3) increament m until m**2

vishalbhardwaj51 + 0 comments That's very smart! :D

an09mous + 1 comment My Python solution: for t in range(int(input())): beg,end=map(int,input().split()) print(int(end**0.5)-int((beg-1)**0.5))

renato314159 + 0 comments doesn't seem to pass 17->24 test case

jzhao728 + 0 comments Yeah this is the method that I used. Ultimately, it's exploiting the fact that squaring is bijective and monotone.

steven_gerazdnn1 + 0 comments That's exactly what I need. Thank you! happy wheels

tchounwhi + 0 comments This is excellent. Very straightforward. The loop solution causes runtime errors in C++. But this solution passes all the cases. Thanks man.

mali_suresh + 1 comment nice! Logic guys

reaped_juggler + 0 comments thanks!

AronTD + 6 comments If you're having trouble with the code timing out (and you're using a loop), realize that you can iterate through square integers instead of every integer. AKA if you find that 4 is a square (sqrt is 2), then the next number to check would be 9 rather than 5 (2 + 1 = 3; 3 * 3 = 9). If 9 is outside of your range, you stop. If not, you continue. The editorial brute forces it and probably wouldn't work.

qubit77 + 0 comments Thanks. Very helpful!

omalsa04 + 2 comments Don't need to iterate at all, you can just use:

`floor(sqrt(b)) - ceil(sqrt(a)) + 1`

daj4n0 + 1 comment it's kind of the same isn't?

when you iterate, your algorithm takes

`log(sqrt(b)-sqrt(a))`

time to find all the square roots between`ceil(sqrt(a))`

and`floor(sqrt(b))`

. which is kind of the same time as calculating`floor(sqrt(b))`

Basically the algorithms are the same, maybe it uses less lines.

sebjc + 2 comments @omalsa04 answer is a single calculation. No matter how far b is from a, it will always remain a single calculation. Thus it's O(1). When you iterate, the calculation will take longer as the distance from a to b increases thus it's O(n) or O(log(n)). e.g. a=3,b=9 will take significantly less time than a=3, b=10000. The running time is dependant on the input if you iterate.

daj4n0 + 0 comments [deleted]daj4n0 + 1 comment Look it in this, way, you could do any algorithm, and put it into a function, inside of a library, then, any algorithm will be O(1) since every algorithm can be done in just one function call.

Its ok, to suppose that system implemented functions are eficient, but you should think they are free.

sebjc + 1 comment It isn't true that an algorithm can be made O(1) by hiding detail in a library or function call. You still have to account for the running time of that function call.

daj4n0 + 2 comments exactly thats my point, all of this solutions are O(log(n)) no O(1)

sebjc + 0 comments Again, that's not true. If you iterate, then the calculation will take longer as the difference between the inputs increases. If you use the equation it is independant of that difference and thus O(1). Consider this code I posted to github. https://github.com/SebastianCarroll/ruby-practice/blob/ff3e4a7bf0da93cdef54f972122fc3a5d86291f5/sherlock_and_squares/sherlock.rb

If you run this you will get something like the png in the output directory which clearly shows that the loop is O(log(n)) whereas the equation is O(1).

ifazk + 1 comment I see what your point is, but some hardware do provide primitives for square roots, so just as addition and multiplication can be thought of as a basic operation, so too can floating point square roots. For example, the Pentium Pro can compute 80-bit floating point square roots in 69 cpu cycles - this is fixed and does not vary with input size.

However, if your Math library does floating point square roots in software rather than in hardware, it probably uses the O(log(n)) Newton method. I belive the sqrt in C++'s cmath actually does square root using Newton method, so in that case it is actually O(log(n)).

sebjc + 1 comment Good Point! I wasn't aware that we used Newton's method for that. However, I don't believe this changes the algorithmic complexity here. When you say Newtons method has complexity O(log(n)), I believe that n here refers to the precision of the number not the size of the input. Thus if you fix the precision (I don't see you wouldn't) then calculation is roughly constant from our perspective. See; http://stackoverflow.com/questions/5005753/what-is-newton-raphson-square-methods-time-complexity/5005879#5005879 and http://en.citizendium.org/wiki/Newton%27s_method#Computational_complexity

ifazk + 0 comments Sorry, I forgot that the n was in precision. O(log(64)) it is then.

erix777 + 1 comment Pretty awesome that nothing beats knowing your math... Can you elaborate why this formula works? Is it a Pythagoras (c^2 = a^2 + b^2) kind of deal? I guess the "+1" is cause the interval is inclusive?

mikeym88 + 1 comment It is called the Intermediate Value Theorem: https://en.wikipedia.org/wiki/Intermediate_value_theorem

erix777 + 1 comment Right. And it will work for projecting intervals from x to y using any function not just y= x^2 here an explanation I liked too https://www.youtube.com/watch?v=g9QRNbJLs94 thanks!

Ayelis + 0 comments Still sad that you have to resort to a theorem to solve the problem. What are computers for if not brute force iteration! ;)

Besides, Watson never told Sherlock that he had to solve each problem in under 10 seconds. The fate of the world is not on the line. So what's the big rush!

vanderhyde + 0 comments This is a good hint. It is essentially what I did, and although it was slow, it didn't time out. This can be improved, however, to O(log n), using binary search through the square numbers. So you can get log time without actually calculating any square roots.

ltoniut + 0 comments Yeah, doing exactly that in C#. Still times out, though. Really frustrating...

RodneyShag + 0 comments Or, instead of iterating through the squares of integers, you can iterate through the square roots of integers as I did in this Java Solution. It makes for simpler code since you just have to count the number of integers between the square roots of A and B

From my HackerRank solutions.

princepatrickan1 + 0 comments Thanks.

markwalton + 3 comments Thanks to everyone who explained the fast solution. I'd like to explain my understanding of it for people who are not grasping how it works. I hope by typing it out I fix in my own mind how to think about problems like this, and explain longhand to others how it works in case the shorthand others are giving isn't clicking with you. Of course this supposes my understadning is correct.

The solution for this problem will be the count of a quantity of integers which are square numbers and have integer square roots. The trick is to not look at the (potentially millions large) range of values we want to examine to see if they are square roots, but to look at the roots they become.

So if you look at the range of all integers,

1 2 3 4 5 6 7 8 9 .... etc,

each of these can be squared to produce a value. Each maps to a 'seemingly random' set of numbers

1 4 9 16 25 36 49 64 81 ... etc

If you had been given the values 20 and 55, and asked to find all the squares in between, you might iterate 20 - 55 and find the sqrt of each number, that's 36 tests adding to the accumulated value each time you find a match.

But, each of the square roots you find in that range will be in a sequence. You will find

sqrt(25) = 5 sqrt(36) = 6 sqrt(49) = 7

for ANY test like this, the results MUST be the squares of a sequence of integers. You can't find the squares of 5,6,8, and 9 in your solution without the square of 7 also being in there. It has to be because you are looking at all numbers in a range.

So, if you find the square roots of your start and end values, that will give you a start and end of this range of integers which provide the squared values in your required range.

In the example I give here, sqrt(20) is between 4 and 5; sqrt(55) is between 7 and 8.

1 2 3 4 * 5 6 7 * 8 9

So in between those, there are 3 values which if you square them will be the 3 square numbers between 20 and 55. Your answer is 3.

This works for every range. So even if you have a billion values in your range, by finding their square roots you find the integers those square roots "surround" and therefore your required result. This is clearly a lot faster than checking each one or trying to create a database of all primes for lookup, or any other method. Find the square root of the two provided values and work it from there.

agamya_29101995 + 0 comments The best explanation I found. Thanks!

amna_khatun1605 + 0 comments This explanation made me understand the logic. Thankyou for sharing!!!

deepchandila07 + 0 comments Awesome explanation !!!

daltyboy11 + 3 comments python3 solution: Count all the integers in the range [sqrt(a), sqrt(b)]

import math t = int(input()) for _ in range(t): a, b = input().strip().split(' ') a = int(a) b = int(b) sqrtA = math.ceil(math.sqrt(a)) sqrtB = math.floor(math.sqrt(b)) print(sqrtB - sqrtA + 1)

m_manoj + 1 comment I wonder the way you solve the problem. How you find the underlying mathematical pattern?

SebastianNielsen + 0 comments The more you solve problems like these, the more likely you are to remember the solution. And by that, the more you practice these kind of problems, the more likely you are to see the pattern from a former problem you have solved.

So if you want to find these "mathematical patterns" keep solving problems, and make sure to understand why it works.

I hope that helped!

jasonmoule + 0 comments Here's a version without imports. The key is that we are only looking for the number of integers in the range that are squares, not the actual numbers themselves. So we just need the smallest possible and the largest possible. Here

`int()`

acts the same as`math.floor()`

.for _ in range(int(input().strip())): a, b = [int(i) for i in input().strip().split(' ')] minSq = int(a**0.5) if (int(a**0.5)**2 == a) else int(a**0.5) + 1 maxSq = int(b**0.5) print(maxSq - minSq + 1)

Amitbanerjee + 1 comment why did you add 1 in the last print statement. I could not understand the reasoning behind that.

jasonmoule + 1 comment It's simply the 'number of items in a sequence' equation, ie how many natural numbers are there in [5..9]? Max-Min+1 or 9-5+1 = 5 for [5, 6, 7, 8, 9]

Amitbanerjee + 0 comments thanks for the clarification. I understood now

devisetty_shash1 + 2 comments import java.io.*; import java.util.*; import java.math.*; public class Solution { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int t = scan.nextInt(); while(t-- > 0) { int a = scan.nextInt(); int b = scan.nextInt(); System.out.println((int) Math.floor(Math.sqrt(b)) - (int) Math.ceil(Math.sqrt(a)) + 1); } } }

Prakash0703 + 0 comments good work

tejasv2098 + 1 comment please explain the logic.thanks in advance

devisetty_shash1 + 2 comments you need to find the number of integers whose squares lie in the given boundary values. Hence, it is the same as finding the number of integers between the square roots of the given boundary values. Since the values are inclusive, floor of the square root of upper boundary is subtracted to the ceil of the square root of lower boundary which gives number of integers between them. 1 is added to include the first one also

hlodoveh + 1 comment And which one is "first one"? Other I understand, ty!

deshmukhprasann1 + 0 comments awesome!!!!

achathukulam + 0 comments good logic.......

RodneyShag + 2 comments ### Java solution - passes 100% of test cases

From my HackerRank solutions.

Simply count # of integers (inclusive) between the square roots of A and B

import java.util.Scanner; public class Solution { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int T = scan.nextInt(); while (T-- > 0) { int A = scan.nextInt(); int B = scan.nextInt(); int numSquares = (int) (Math.floor(Math.sqrt(B)) - Math.ceil(Math.sqrt(A)) + 1); System.out.println(numSquares); } scan.close(); } }

Let me know if you have any questions.

tartarJR + 1 comment Could you please explain the logic ? @rshaghoulian

RodneyShag + 1 comment Hi. Try to understand the main concept first instead of the code, that is, try to understand it mathematically.

Counting the number of squares between A and B is somewhat harder since we have to calculate squares and see which ones fall in between the desired range. Instead of calculating squares, we can take the square root of everything. That is, take the square root of A, take the square root of B, and simply see how many numbers fall in between this range.

So if, A is 9, and B is 16, we have the range [9,16]. After taking the square roots, we have the range [3,4], which we just count how many numbers are in that (inclusive) range, which is 2.

If instead our original range was [8,17], taking the square roots would still give [3,4] due to the Math.ceil() and Math.floor() functions, and we have 2 numbers in that (inclusive) range.

luckyguy73 + 0 comments brilliant, thank you

**php solution**<?php $handle = fopen("php://stdin", "r"); fscanf($handle, "%d", $n); for ($i=0; $i < $n; $i++) { fscanf($handle, "%d %d", $b, $e); echo floor(sqrt($e)) - ceil(sqrt($b)) + 1 . "\n"; }

palashrawat7 + 1 comment Please explain:-

int numSquares = (int) (Math.floor(Math.sqrt(B)) - Math.ceil(Math.sqrt(A)) + 1);

Lets say we have to calculate from 26 to 70.

Math.floor(Math.sqrt(B)) would give 8.

Math.ceil(Math.sqrt(A)+1)would give 7

So int numSquares would be=8-7 which is equal to 1. Which will be wrong.

It should be "[36,49,64]" totalling to 3.

RodneyShag + 1 comment Math.floor(Math.sqrt(B)) = Math.floor(Math.sqrt(70)) = 8 Math.ceil(Math.sqrt(A)) + 1) = Math.ceil(Math.sqrt(26)) = 6

Then do 8 - 6 + 1 = 3.

You had the parentheses in the incorrect place.

palashrawat7 + 1 comment Why are you adding 1 to it?

RodneyShag + 1 comment It is because we are tring to do 6 to 8

**inclusive**, which is 3 numbers: 6, 7, 8. The math just works out that way.palashrawat7 + 0 comments Thanks a lot.

polat10207 + 0 comments def squares(a, b): if(math.sqrt(a)==int(math.sqrt(a))): a= int(math.sqrt(a)) else: a=int(math.sqrt(a))+1 if(math.sqrt(b)==int(math.sqrt(b))): b=int(math.sqrt(b))+1 else: b=int(math.sqrt(b))+1 return b-a

*python 3 solution*

donadivarun + 0 comments one-liner in python:

def squares(a, b): return (int(math.sqrt(b))-int(math.sqrt(a))+1) if (math.sqrt(a)==int(math.sqrt(a))) else int(math.sqrt(b))-int(math.sqrt(a))

d_silva + 1 comment 1 line solution in Java:

static int squares(int a, int b) { return ((int) Math.floor(Math.sqrt(b)) - (int) Math.ceil(Math.sqrt(a)) + 1); }

shyam1_ss15 + 0 comments dude can You explainne the code, I have done with loops, But these math things goes overhead

shravil_potdar + 3 comments Getting 'Terminated due to timeout'... Python3

import math n=int(input()) for i in range(n): u,l=input().strip().split(' ') u,l=int(u),int(l) count=0 for x in range(u,l+1): if math.sqrt(x).is_integer(): count+=1 print(count)

jessedgb + 0 comments Same

sulaimanr29 + 0 comments yeah same

marco_a_strauss + 0 comments same problem using while. cannot complete due to timeout

def squares(a, b): c = 0 i = a while i <= b: if math.sqrt(i) == math.floor(math.sqrt(i)): c += 1 i += 1 return c

Sort 643 Discussions, By:

Please Login in order to post a comment