Power Function in logarithmic time [Technique Tuesdays]
This is a neat little optimization that will help you a lot.
To learn more about the newsletter, check our detailed About Page + FAQs
To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.
Recommend this publication to Substack over here
Imagine I gave you 2 positive ints m and n-
And I asked you to compute m^n.
How would you do it?
The simple way is to rely on the definition. Since m^n = m*m*m …(n times), we can write a loop to solve this.
However, this would have O(n) time complexity and can be very slow.
Today I have a technique that will solve this in logarithmic time. Not only is this much quicker, but this technique can also be tweaked and applied to optimize a lot of other algorithms. This means that building your skills with this is a must.
You’re lucky because this technique has a huge ROI. A little practice with this, and you’ll see amazing results.
Highlights
The technique- We can leverage some basic math to speed up our work. Notice if our input -n- is even then we can right it as 2k, where k is an int. If n is odd- then we write it as 2k+1.
Slow way- m^n= m* m^(n-1) Our way- If n is even, m^n = m^ 2k= m^k * m^k If n is odd, m^(2k+1)= m* m^2k ...we know where to go from here
What does this achieve- Let’s analyze the recursive call stack/number of instructions that our slow approach uses. It goes 1 at a time. Compared to that, our speedy way halves the instructions. Take a second to understand why.
For your interview/exam- In your interviews/computer science exams, people will ask you this problem to test your recursive skills. Make sure you go through our Archives and read through my older posts on recursion. More established places will ask you to let n be any integer, instead of just a positive one. How would you solve that? Take a crack at it. Once you’re done, look at my solution for this problem here.
Why this is relevant to the broader field- Take a step back, and look at how we solved this problem. It might not be immediately obvious to you, but this question is a very interesting variant of the divide and conquer technique. D&C is one of the most powerful techniques in recursive problem solving and coding. Understanding this technique will help you get better with D&C.
Special Challenge- I’ve already given you the 2 most common variants of this problem. There is a 3rd tricky variant, which you might be asked if your interviewer/prof is feeling particularly sadistic. My AI prof asked this in class, and it definitely messed up a lot of people. Create a fast pow that works with n being any real number not just ints.
Do your best to come up with that solution. It’s an interesting problem that really works your problem-solving muscles. I really like it because it doesn’t need you to know any specific data structures or patterns. Just normal everyday tools that you would use in your day-day work applied in a creative manner.
I created Technology Interviews Made Simple using new techniques discovered through tutoring multiple people into top tech firms. The newsletter is designed to help you succeed, saving you from hours wasted on the Leetcode grind. I have a 100% satisfaction policy, so you can try it out at no risk to you. You can read the FAQs and find out more here. Use the button below to get 50% off for upto a whole year.
This is a limited-time offer, that I’m running to celebrate my almost 50 questions completed. Take advantage of it by clicking the button above.
Before proceeding, if you have enjoyed this post so far, please make sure you like it (the little heart button in the email/post). I also have a special request for you.
***Special Request***
This newsletter has received a lot of love. If you haven’t already, I would really appreciate it if you could take 5 seconds to let Substack know that they should feature this publication on their pages. This will allow more people to see the newsletter.
There is a simple form in Substack that you can fill up for it. Here it is. Thank you.
https://docs.google.com/forms/d/e/1FAIpQLScs-yyToUvWUXIUuIfxz17dmZfzpNp5g7Gw7JUgzbFEhSxsvw/viewform
To get your Substack URL, follow the following steps-
Open - https://substack.com/
If you haven’t already, log in with your email.
In the top right corner, you will see your icon. Click on it. You will see the drop-down. Click on your name/profile. That will show you the link.
You will be redirected to your URL. Please put that in to the survey. Appreciate your help.
In the comments below, share what topic you want to focus on. I’d be interested in learning and will cover them. To learn more about the newsletter, check our detailed About Page + FAQs
If you liked this post, make sure you fill out this survey. It’s anonymous and will take 2 minutes of your time. It will help me understand you better, allowing for better content.
https://forms.gle/XfTXSjnC8W2wR9qT9
I see you living the dream.
Go kill all and Stay Woke,
Devansh <3
To make sure you get the most out of Technique Tuesdays, make sure you’re checking in the rest of the days as well. Leverage all the techniques I have discovered through my successful tutoring to easily succeed in your interviews and save your time and energy by joining the premium subscribers down below. Get a discount (for a whole year) using the button below
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75