DollarAkshay 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 Very nice! Haven't the constraints tests, but http://goo.gl/dHHG60. =D
Singhalr31 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?? :(
himanshukumar161 With more and more practice, you come to learn these things. Also depends on math skills.
maxpayne2502 no shortcuts just practice without seeing the discussion and after u have solved the question ,u can see the discussion for better answer
Singhalr31 i solved it using loops and if statements but the solution was not enough to execute the problem in less than the fixed time. So then only i came here to find the better solution and found this amazing formula and wondered how to think like this..lol
hroger19 For me, I looked for a pattern and wrote my algorithm based on that pattern. Still not as efficient if it ends up being the last # is the sq integer as my pattern was based on differences between each sq integer.
yabhi565 It's not a formula though. It's the result of visualization reasoning only 😉
nitinshaily0 you just have to think from machines perspective in these type of question if you will start iterATing through all no. it will sure consume a lot of machine time so think abt solution where you can skip some iteration like this guy... by the way ma python soln:
def squares(a, b):
sq=0 while(a<=b): if str(math.sqrt(a))[-2:]==".0": sq+=1 a=(a//math.sqrt(a)+1)**2 else: a+=1 return sqrishabh_shailes1 From where you came up with this formula? a=(a//math.sqrt(a)+1)**2
sivasakthisairam really great sir
ricardoreich Why is this faster than for i in range(a,b): if math.sqrt(i) % 1 == 0: sq += 1
? I, know it is faster just dont understand why.
Juaner_ you can tell if a float is an integer by:
if float.is_integer(-number you want-):
ramzes_93 you are not alone bro)
schehrbanokhan I feel you. The good thing is that the more you do it the more you will learn. I know its hard but persist, dont get frustraed write down cases and figure out what works, you will start to see a pattern and that will help you answer the question. It tooke me 2.5hrs to do this question, in this time I got frustrated and left for 15 mins and then came back and did the whole thing again and finally came up with an answer.
naveenkm36 practice by writing the solution and absorb the pattern from the written solution
yabhi565 Just begin with the (basic) reasoning that initially comes to your mind. As you proceed and visualize the relations between things, you will be amazed to see that you can actually figure out optimized solutions. Don't get carried away with fancy one-liners. Time-optimization is more important. Once the habit of analyzing numbers in programs gets you, you too can rock!
mostafa_asg How you find this formula? why this formula is correct?
alexndreazevedo Is simple! Count all integers found between the square roots given.
StephnR Can someone explain this? I do not understand how this makes sense
Arius 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 Perfect explaination
Icarus_XXII Still makes no sense to me... :(
suyashsngh Find the sqrt of ends and subtract it u will get the number of perfect squares in between them
svijay1991 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 do not forget that 2-2 + 1 wich equal to 1 and it still right
vi123 [deleted]
cesarjom 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 true
vvbhandare Perfect One. Please tell me how did you find the formula?
caccaacccaaa Perpect !!
rahulmurugan perfect
itsmeguptapankaj right
kcsarrdah wow...can you tell me how you figured this out?
rahulkumar_cs17 It's correct dude.
suppose A is equals to B and A=B=5
square root of 5= 2.something
Floor(2.something)=2; Ceil(2.something)=3; therefore, count = 2-3+1 =0
borse1012 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 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 Thats why I love maths.
thepuja4266 why are you taking floor of larger number and ceil of smaller one??
saichakri test cases are failing
vi123 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 This is some strange math.
Alexvhr 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 = x2. 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 Very nice explanation
Maverick_911 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 [deleted]lawless_war1ock only first 2 cases and the last 2 cases run others don't
abhiroyg It's because if you are storing in int you are internally applying floor. Here ceil is also needed.
sakshamgoyalswm 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 Nicely Explained. Thanks.
irkjsdb Very helpful
greenhorn101 Thanks for this explanation! That was very helpful.
cdr95 [deleted]
abhishekramkumar Great explanation Alex
spartacus_arena Is this necessary to go too deep to understand these concept?
thong1411998 Very great explanation , Thank you very much
asadjivani Amazing observation. .Thanks alot.
kharatpriyank Amazing explanation!
Mrsolodolo I think inverse function should be sqrt(y) ??
b_s_apsara_july Finally understood how this formula came...Very nice explanantion....Thanks
code_school_9 [deleted]DHARININEHRU nice explanation. Thanks a lot
ashishgoyanka Great Explaination
hemanth_savasere nice and good explanation
alamb76 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.
ramzes_93 we don't need code bro, we need explanation) to get and understand problem) but anyway thanks
desi_duuh As a person who doesn't prefer Math, THANK YOU!
eunha0174 Very thanks.. Math knowledge necessary to solve this problem.
kshuvo96 thank u well explain
kushagrapathak91 thank you very much it helped alot.
mukuldutt1234 lol thankYOU <3 (int)Math.floor(Math.sqrt(b))-(int)Math.ceil(Math.sqrt(a))+1;
syedjawadakhtar Amazingly explained!!! Thanks!!
neha86_arora Its interesting.. difficult at first and simple when understood..
abhinashbihari11 Thanks for u r explanation
codedas_dyanesh 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 Thank you so much for explaining it simply.
kevinbrewer04 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, 16Our objective is to find how many numbers in the sequence
4 5 6 7 ... 15 16are 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 sequence2 3 4, which are the square roots of the square integers4 9 16, which are the three square integers in our original sequence4 5 6 7 ... 15 16!
osamaejaz1 thank you :)
cary_a_miller Ok, that was an excellent explanation. Thank you!
Divas0103 amazing .. its really so helpful.
142Tanjul Excellent explanation
kirubha_16p119 this was very useful thank you
smarsh Plain english and clear. Not something you see everyday here on Hacker Rank. Thank you!
manishmeshram51 thanks :)
reaped_juggler never a problem :) keep coding
menyus_szelei Best explanation! Thx
avinashp999 one of the best explanation you can get.
reehalnavi [deleted]reehalnavi int check(int a,int b) {
int m,x; float n; m=sqrt(a); n=sqrt(a); x=sqrt(b); if(n>m) m=m+1; return x-m+1;}
zaynchavan How did you come to the conclusion of this formula? Please tell.
reehalnavi which formula? Are you asking for a single line or for whole of the function?
therealsanjeev bro if possible, can u explain us?
reehalnavi just read the above explanation given by "kevinbrewer04"...
srivastavahars13 excelent solution...
dayal_ruchi99 Thank you for that excellent explanation.
tanya_dixit17 excellent explanation :)
ranjith16112000 Very nice Thank you
aayushARM Damn! Far better than iterations...
manasaedula11 wow simly superb,thanks for the explanation
justnotcoding You deserve a medal for this extremely simple explanation. Well done.
ajboss perfect! i went all the way through n got timeout
mchisty [deleted]pankaj_mittal372 thanks!
cyberajit Awesome! ... that helped! :)
josergc Thank you very much for the explanation!
saiteja_malladi Very nice one. Thank you...
sunil98meena how to see which no. is integer which is not??
aakankshashastr1 awesome!!
hetp111 Perfect...!
lemanisar23 great explanation:)))
zeus_mmmut Clear as Crystal
Alexvhr 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 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 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 your method will run at atleast
\Omega(n^{1/2})time. Which is way higher than this\theta(1)timeAronTD He's not doing any iteration. He's just subtracting the lowest possible sqrt from the highest possible sqrt.
sidmeister "we can find the square root of first square number in given range and then
increase it by one untill its square is not exceedingthe given range."AronTD 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 Ah. My bad.
dannyv573 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 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 great coding!
Epshita Nice coding!
uwaisulde Dude its awesome.great work
karananandkk range += temp*2 ;why the above code is used ?
manojbabu115 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 [deleted]
nandhini_r_20151 can you please explain it ...
positivedeist_07 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 My bad!! I found out it causes time out :/ So yeah, the double increment is necessary!
Striker437 superb logic
kickkick range += temp*2 ; can u explain this step;
manojbabu115 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 [deleted]nishantraj140211 if range is 9 then range=9+3*2 range=15 and there is no perfect square b/w 10 and 15
shivam_deep Thanks!
reaped_juggler welcome !
siddhartkothari1 I didn't realize that. Thanks for explanation.
aashishbuddy1234 nice observation..thanks for explaining!
cbhawana603 amazing
sayakhaldar640 Nice one brother!
Shaikatpal56 Awesome bro
maklaka 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 range += temp*2 ;
Dude can you please explain !
mdazhar0m123 [deleted]mdazhar0m123 let range =4 so you will reach now to 8(4+2*4) nearest to another perfect square
Loydik I don't know how I did not think about this!! Came up with a complicated solution (relative to yours) instead :(
Kuriocity [deleted]
piyusman [deleted]alaniane 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 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 Thank you .Great code !!
m_bagus_oka Brilliant.
3yakuya I was thinking exactly the other way round - results were awful. Thanks!
flawlessvoid This is beautiful. It doesn't just solve the problem; it understands the problem deeply.
iGbanam This is sublime!
lawless_war1ock isn't rounding of the(floor(sqrt(b))-ceil(sqrt(a))+1)); necesasary>?/?
alacret That ceil part is a minus (-) operation instead of a sum (+)
JonAmazon 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 This just means that the solution can fail if you manipulate
float... using another type likedecimalshould work fine.
evilcat [deleted]zac_c_petit This is illegible. I don't care how efficient the solution is if I can't read it.
Ayelis 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 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 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 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 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 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 google search engine could be written in one line by eliminating space and \n too
zac_c_petit 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 exactly
Ayelis Agreed. "1 line" + "2 semicolons" = "3 lines". No matter how you .slice() it.
madhan_coder I am not able to use sqrt here.
kamalraghav 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 [deleted]
dbarkman Brilliant!
raphnguyen This solution is genius. Always awesome to find room for more optimization.
Kronodeus Frustratingly smart.
ashish1702 Thanks !
congtrang009 perfect!
amitkm9204 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 Your formular is great. Thank you
RodneyShag 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 Thank you very much for the trick!
sanyachaba26 test case #3 is working with this solution?
mahak1 what is the reason for adding 1?
16bit155 can you please tell me that why you have written +1 in the end?
Learner_V1 Awesome
vishwasjha17 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 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 can u explain the logic behind it?
Mrsolodolo No to do list(map), map will return list only...
daiict_201712029 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 It's amazing. thank you
krishbht15 The best logic
rajat_yadav 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 That's very smart! :D
an09mous 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 doesn't seem to pass 17->24 test case
jzhao728 Yeah this is the method that I used. Ultimately, it's exploiting the fact that squaring is bijective and monotone.
steven_gerazdnn1 That's exactly what I need. Thank you! happy wheels
tchounwhi This is excellent. Very straightforward. The loop solution causes runtime errors in C++. But this solution passes all the cases. Thanks man.
mali_suresh nice! Logic guys
reaped_juggler thanks!
1VaibhavMehta One direct solution is:
static int squares(int a, int b) { int count=0; for(int i=1;i<=Math.sqrt(b);i++) { int x= i*i; if((x>=a) && (x<=b)) count++; } return count; }
hackkerguy11 for anyone try in C++ :
int squares(int a, int b) { int count = 0; int i = sqrt(a); while(i <= sqrt(b)) { if(i*i >= a && i*i <= b) { count++; } i++; } return count; }
rohit_sun_india That's a Sherlock way to solve! Thanks for sharing.
hsrivastava96 Hi, can you please explain the logic behind taking just the difference ceil and floor of roots of a and b
AronTD 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 Thanks. Very helpful!
omalsa04 Don't need to iterate at all, you can just use:
floor(sqrt(b)) - ceil(sqrt(a)) + 1
daj4n0 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 betweenceil(sqrt(a))andfloor(sqrt(b)). which is kind of the same time as calculatingfloor(sqrt(b))Basically the algorithms are the same, maybe it uses less lines.
sebjc @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 [deleted]daj4n0 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 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 exactly thats my point, all of this solutions are O(log(n)) no O(1)
sebjc 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 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 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 Sorry, I forgot that the n was in precision. O(log(64)) it is then.
erix777 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 It is called the Intermediate Value Theorem: https://en.wikipedia.org/wiki/Intermediate_value_theorem
erix777 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 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 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 Yeah, doing exactly that in C#. Still times out, though. Really frustrating...
RodneyShag 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 Thanks.
markwalton 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 The best explanation I found. Thanks!
amna_khatun1605 This explanation made me understand the logic. Thankyou for sharing!!!
deepchandila07 Awesome explanation !!!
pavankrishna_te1 Please get some energy and read this paragraph. This is so simple after readin the problem. By THE way, this guys intent is not to showcase his output or code. He tries to explain the logic of the code which is very useful
daltyboy11 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 I wonder the way you solve the problem. How you find the underlying mathematical pattern?
SebastianNielsen 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 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 asmath.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 why did you add 1 in the last print statement. I could not understand the reasoning behind that.
jasonmoule 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 thanks for the clarification. I understood now
devisetty_shash1 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 good work
tejasv2098 please explain the logic.thanks in advance
devisetty_shash1 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 And which one is "first one"? Other I understand, ty!
deshmukhprasann1 awesome!!!!
achathukulam good logic.......
Sort 874 Discussions, By:
Please Login in order to post a comment