Valid Perfect Square - Leetcode 367 - Binary Search (Python)

Master Data Structures & Algorithms for FREE at AlgoMap.io/
Code solutions in Python, Java, C++ and JS for this can be found at my GitHub repo here: github.com/gahogg/Leetcode-Solutions/blob/main/
Complete DSA Pathway Zero to Hero: kzbin.info/aero/PLKYEe2WisBTFEr6laH5bR2J19j7sl5O8R
Please check my playlists for free DSA problem solutions:
kzbin.info/aero/PLKYEe2WisBTGq9T0wPulXz1otUsVeOGey
kzbin.info/aero/PLKYEe2WisBTFlP0RlwfwPrdkvHrcTBUg-
kzbin.info/aero/PLKYEe2WisBTEK8_GVXySX9aDWBHk5fGwQ
kzbin.info/aero/PLKYEe2WisBTFZH-p9jgAOwtHy9_LGI28W
kzbin.info/aero/PLKYEe2WisBTH7I9sCPjSZCs-iBAH4ybmS
kzbin.info/aero/PLKYEe2WisBTH601scI_A008gm34oARlIp&si=DnCpq_RiFkObYn7p
kzbin.info/aero/PLKYEe2WisBTF21RGRtZfGGolpHmca_d3N
kzbin.info/aero/PLKYEe2WisBTH48RzVCL_LQrGW-ahPY44S
kzbin.info/aero/PLKYEe2WisBTHcWHAGWvKJuVMu5ElMA18M
kzbin.info/aero/PLKYEe2WisBTEY7eJBW7W-jbxlXCGb928P
kzbin.info/aero/PLKYEe2WisBTHCmJ6IfEMjg8o--Bvfc5gt
kzbin.info/aero/PLKYEe2WisBTFw-XWc-kwS3dkQeeSmvpg5
My Data Science & ML KZbin Playlist: kzbin.info/aero/PLKYEe2WisBTECZ8mZCfFxzrBBuGrS1Gfu&si=hspEoaBIyVLV_TyC
Learn Python and Data Science FASTER at mlnow.ai :)
Support the content: kzbin.info/door/JublDh2UsiIKsAE1553miwjoin
Follow me on Instagram: greghogg5
Connect with me on LinkedIn: www.linkedin.com/in/greghogg/
Follow me on TikTok: www.tiktok.com/@greghogg5
Coursera Plus: imp.i384100.net/P0E3J6
My Favorite Courses:
Data Structures & Algorithms:
- UCalifornia San Diego DSA: imp.i384100.net/LP31oV
- Stanford Algorithms: imp.i384100.net/vNBoxd
- Python Data Structures: imp.i384100.net/NkZn47
- Meta Coding Interview Prep: imp.i384100.net/Y96rBJ
Python:
- UMichigan Python for Everybody: imp.i384100.net/QOLM73
- Python Mastery from MLNOW.ai: mlnow.ai/course-material/python/
- Google IT Automation w/ Python: imp.i384100.net/5g6Xyj
Web Dev / Full Stack:
- Meta Front-End Developer: imp.i384100.net/q4Jemy
- IBM Full Stack Developer: imp.i384100.net/Gj9dMn
- Meta Back-End Developer: imp.i384100.net/xkW0r5
- John Hopkins HTML, CSS & JS: imp.i384100.net/QyoRAA
- IBM DevOps: imp.i384100.net/kjd2r0
Cloud Development:
- AWS Fundamentals: imp.i384100.net/anqBjZ
- GCP Cloud Engineer: imp.i384100.net/g1jvqB
- Microsoft Azure Fundamentals: imp.i384100.net/EKm5O4
Game Development:
- Michigan State Unity Development: imp.i384100.net/6eOBnr
- UColorado C++ for Unreal Engine: www.coursera.org/specializations/cplusplusunrealgamedevelopment
SQL & Data Science:
- SQL by MLNOW.ai: mlnow.ai/course-material/sql/
- Python for Data Science by MLNOW.ai: mlnow.ai/course-material/datascience/
- Google Data Analytics: imp.i384100.net/1rkWAR
- IBM Data Science: imp.i384100.net/P0ZRL6
- IBM Data Engineer: imp.i384100.net/4PbZyZ
Machine Learning & AI:
- ML Mastery at MLNOW.ai: mlnow.ai/course-material/ml/
- ML w/ Andrew Ng: www.coursera.org/specializations/machine-learning-introduction
- Deep Learning w/ Andrew Ng: imp.i384100.net/a1kjJj

[@GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[@LelouchVDK]

I might be dumb, but putting it on the internet anyway. But wouldn't any square of an integer larger than the half of the original number already be bigger than the original number, meaning you could set the initial range to be from 1 to num // 2. Either way amazing question with an awesome solution from you

[@GregHogg]

Yes you could probably optimize the end range quite a bit. However because it's log and dividing by two each time, you'll only spare one or two iterations max anyway. Excellent observation. Thanks so much!

[@brycejohansen7114]

You could use Newton's Method which is O(log log n) because it converses quadratically.

[@GregHogg]

Yeah very true!

[@acceleratedofficial1576]

For java users Few tuning in this solution 1st =divide upper bound by 2 , as it will reduce total length for binary search 2nd = use long to store mid*mid

[@Jonas-gm4my]

The nth perfect square is the sum of the first n odd number, cant we just subtract odd numbers while the number is bigger or equal to zero and then check whether we are at 0 at the end?

[@kumarashutosh-p3n]

please explain leetcode's "LAST DAY WHERE YOU CAN STILL CROSS" or "MINIMUM COST TO MAKE ARRAY EQUAL"

[@GregHogg]

I'll try to at some point :)

[@mjanish9836]

brother, you can keep end = num//2 it actually reduces time

[@GregHogg]

Cool thanks :)

[@Xagittarius]

Cloud you guide a zigzag conversation

[@GregHogg]

What?

[@Xagittarius]

@@GregHogg a zigzag conversation from leetcode

[@GregHogg]

@@Xagittarius I'll try to take a look at some point :)