When we update hi = mid or lo = mid, they will never cross each other. They will ultimately become equal, i.e., hi = lo. And stop. So, in this case while(lo < hi) can be used. If you are updating like: lo = mid + 1, and hi = mid - 1, then lo & hi will cross each other, and you can use while(lo
@@KnowledgeCenter Thanks! This is great explanation! I saw LC 69 solution and it said return (lo-1) and did not fully understand its significance until you pointed out: hi = lo-1 (the first instance they cross) in both of your replies. Also, when you are checking in duplicates (get range of a repeating elem), then eventually, a[lo] == a[mid] (or, a[mid] == a[hi[), so we have to use while (lo
Thank you sir for great explanation ! Sir, as only square can overflow, why should we write long long for mid as well ? Mid shall always lie within the range so, writing int for mid should work, But is showing run time error for: bool isPerfectSquare(int num) { int last_dig = num % 10; if(last_dig == 2 || last_dig == 3 || last_dig == 7 || last_dig == 8) return false; int left = 1; int right = num; while(left num) right = mid-1; if(sq < num) left = mid + 1; } return false; }
Your code has 2 mistakes: (1). never calculate mid as mid = (left + right)/2; // As left + right can be more than INT_MAX. Division is performed after adding (left+right). (2.) If you multiply 2 ints or take square of a int and assign it to a long long, first it will be calculated as int only then moved to long long. Example: C++: ------- int num = 10; long long x = num * num; * Assembly: ------------------- mov DWORD PTR [rbp-4], 10 mov eax, DWORD PTR [rbp-4] imul eax, eax mov QWORD PTR [rbp-16], rax Here when I write int num = 10; Move the 32-bit integer representation of 10 into the 4 bytes starting at the address in rbp. (DWORD PTR represents 4 bytes) Then this value is moved to 'eax'. eax is holding 4 bytes representing 10. Then you see -- imul eax, eax It means multiply contents of eax with eax ... So, eax was holding 10. Now eax is holding 10*10 i.e., 100. So, same register is holding the square. Then, the result is assigned to long long x. mov QWORD PTR [rbp-16], rax Here QWORD PTR denotes 8 bytes. So, result is moved to 8 bytes starting at rax. In Short, before assigning square of int to long long variable, first its calculated as int only. Then moved. So, you will get the error. So, make correction to you your code based on both the points I have mentioned.
Yes that is my point 1. But, that will not solve the problem completely, thats why there is point 2.(Although if point 2 is followed, in this this case point 1 is not required.). But, still good to stick to it.
Thanks for a great explanation with diagrams! A similar problem is LC 69 (Squaare root of non-negative num). While we are on the topic of binary search, you can also do LC 668 (kth smallest in multiplication table)? I would like to hear your explanation of count of numbers in a mul table up to a certain target num. Thanks!
Thanks. Yes prob 69 looks almost exact problem like this one. Even code would be almost identical. Just 1 extra thing would be that sq = mid*mid may not exactly match num. So, at the end of the loop return hi. 668 looks a bit tougher than this problem, but Binary search applies there as well. I'll create a video on that, most likely after May challenge. immediately after that.
Please check your while loop, may be its not getting terminated. Are you setting l = mid instead of lo = mid + 1, or r = mid instead of r = mid - 1, because our while loop check is while(l
I think when u are calculating mid: you are subtracting 1 instead of L(lowercase) from right i.e -> long mid = l + (r-1)/2 instead of long mid = l + (r-l)/2 because of which you are getting TLE (time limit exceeded)
@@kiranyadav4721 You are mistakenly subtracting ONE (1) while calculating mid, you need to subtract L(lowercase which is left). Write -> long long int mid = l + (r - l)/2. Hope this resolves TLE.
Hello, I am Sahil from India. I am a pre final year student in NSIT , New Delhi , India. These days i am a bit stressed because of stuck at home and now not able to focus on Competitive Programming. I had already solved about 80-90 problems on Leetcode but still unable to many of problems in April Long challenges , many other problems on leetcode and mostly able to solve 1 or 2 problems on codechef or codeforces challenges . The question solved on leetcode by me are mostly medium level and very few of them are hard also. So could you please help me . Will you be my mentor
