[Solution]Problem 79: Checking for a value[Facebook/Meta]
Math, Problem Solving, Logic Operators, Boolean
Hey, it’s your favorite cult leader here 🐱👤
On Thursdays, I will send you a problem + its solution. These solutions will help you reinforce your fundamental concepts, improve your problem-solving, and kill those Leetcode-Style Interviews. 🔥🔥💹💹
To get access to all my articles and support my crippling chocolate milk addiction, consider subscribing if you haven’t already!
p.s. you can learn more about the paid plan here.
This solution is going to be a deceptively simple one in terms of code.
But the build-up to the solution really packs a punch. It’s a technique you will see all the time in computational problem-solving. This question will serve as an introduction to it.
Hope you’re excited about it.
Problem
Given three 32-bit integers x, y, and b, return x if b is 1 and y if b is 0, using only mathematical or bit operations. You can assume b can only be 1 or 0.
Step 1: Putting the Pieces on the board
Here is all that we have been given about the problem-
No control structures (if/else etc) are allowed.
We know that out of the three numbers, one of them is a binary. This is likely going to be significant. The question hints at this further, by telling us that we are allowed to use bit operations.
So how can we proceed? Let’s approach this by breaking this into various components. Then, we can solve these smaller subproblems and combine it into a bigger result.
Step 2: Returning the right value for x
So how can we return the right value for x specifically?
We know that x follows 2 parts- return x if b==1 and y otherwise. Since we are only looking at x right now, let’s put the second condition on the back burner. We will now reframe this subproblem as- return x if and only if b==1. Else return something else.
How can we return this? An easy way to accomplish this will be to use the following computation-
return x*bGreat. Now onto subproblem number two. How do we return the right value for y? Take a second to think before we proceed.
Step 3: Returning the right value for y
Did you actually try to solve this?
You’re not cheating me, you’re only cheating yourself.
Let’s go back to the drawing board. Just like with y, we can create a simpler subproblem to solve- return y if and only if b==0. Else return something else.
This will be solved easily if we did the following-
return y * (1 - b)We have two easier subproblems solved. So how can we combine these to come up with our final solution?
Step 4: Creating our final solution
How can we combine the two subsolutions to create our final solution?
Notice that the two solutions kind of complement each other. One can be triggered when the other’s win condition is not met. To elaborate on this let’s observe at the following-
b==1- x*b is x and
y * (1 - b) is 0.b==0- x*b is 0 and
y * (1 - b) is y.
Thus, we can combine them using simple addition. That will give us the final code.
Step 5: Coding it Up
Our final code looks like this-
def switch(x, y, b):
return (x * b) + (y * (1 - b))Take notes of multiplication by 0s and 1s, because you will see this technique a lot. For example, feature detection algorithms for images use a matrix of 0s and 1s (and other values as needed) to extract the features. Learning to manipulate values by applying masks of 0s and 1s is a very potent technique that you should master.
Time Complexity- O(1)
Space Complexity- O(1)
Loved the post? Hate it? Want to talk to me about your crypto portfolio? Get my predictions on the UCL or MMA PPVs? Want an in-depth analysis of the best chocolate milk brands? Reach out to me by replying to this email, in the comments, or using the links below.
Stay Woke,
Go kill all,
Devansh <3
Reach out to me on:
Small Snippets about Tech, AI and Machine Learning over here
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