[DSA in Python] is_even.py
This was the second exercise of Chapter 1 (Python Primer) in the book
'Data Structures and Algorithms in Python' by Goodrich et al.
Problem: "Write a short Python function, is_even(k), that takes an integer value and returns True if k is even, and False otherwise. However, your function cannot use the multiplication, modulo, or division operators."
Potential Solutions:
This was a bit harder to solve without using multiplication, modulo, or division operators. For example, we can easily determine if a number k is even by returning k % 2 == 0. This is the modulo operator approach:
This function says that any number that can be divided by 2 without leaving a remainder (divisibility) is even, otherwise, it is odd.
Another approach would be to use both the multiplication and the division operators. One would simply need to divide k by 2 and then multiply the quotient by 2. The product would then be compared to the original input k. If they are equal, then k is even, otherwise, it is odd.
However, we cannot use these operators. What should we do then?
Solutions:
When we count numbers, i.e. 1, 2, 3, 4, 5, one can see that there is a pattern. The first number is 1, which is an odd number. The second number is 2, which is an even number. The third number is 3, which is an odd number. This pattern of switching between an odd number to an even number and then back again when counting can be quite useful information on determining if a certain number is even or odd.
In other words, we are basically tracking which number is even or odd. How do we track it? We use a boolean variable that can serve as a flag.
In this function, we first set the flag to be False because the first counting number will always be an odd number (i.e. 1). Thus, it would make sense to start iterating at 2. We then make two checks and change the value of the flag accordingly. If the flag is currently set to False, then it implies that we have just passed an odd number. Therefore, it means that the current number that we are at should be an even number. If the flag is currently set to True, then that means we just passed an even number. And so, the current number we are at should be an odd number.
As one can see, our boolean variable flag follows along with the pattern of even/odd when iterating by switching between True and False, where True indicates evenness and False indicates oddness.
Another approach that does not use the multiplication, modulo, and division operators would be to use the bitwise operator &. This an esoteric approach because we are dealing with bits. In short, only odd numbers will have their lowest-order bit to be set. So if we do k & 1, we will be able to get the lowest-order bit of number k. We indicate the lowest-order bit to be set if it is 1. However, if the lowest-order bit is 0, then that means that the number is even. An example would be clearer:
Remarks:
Problem: "Write a short Python function, is_even(k), that takes an integer value and returns True if k is even, and False otherwise. However, your function cannot use the multiplication, modulo, or division operators."
Potential Solutions:
This was a bit harder to solve without using multiplication, modulo, or division operators. For example, we can easily determine if a number k is even by returning k % 2 == 0. This is the modulo operator approach:
This function says that any number that can be divided by 2 without leaving a remainder (divisibility) is even, otherwise, it is odd.
Another approach would be to use both the multiplication and the division operators. One would simply need to divide k by 2 and then multiply the quotient by 2. The product would then be compared to the original input k. If they are equal, then k is even, otherwise, it is odd.
However, we cannot use these operators. What should we do then?
Solutions:
When we count numbers, i.e. 1, 2, 3, 4, 5, one can see that there is a pattern. The first number is 1, which is an odd number. The second number is 2, which is an even number. The third number is 3, which is an odd number. This pattern of switching between an odd number to an even number and then back again when counting can be quite useful information on determining if a certain number is even or odd.
In other words, we are basically tracking which number is even or odd. How do we track it? We use a boolean variable that can serve as a flag.
In this function, we first set the flag to be False because the first counting number will always be an odd number (i.e. 1). Thus, it would make sense to start iterating at 2. We then make two checks and change the value of the flag accordingly. If the flag is currently set to False, then it implies that we have just passed an odd number. Therefore, it means that the current number that we are at should be an even number. If the flag is currently set to True, then that means we just passed an even number. And so, the current number we are at should be an odd number.
As one can see, our boolean variable flag follows along with the pattern of even/odd when iterating by switching between True and False, where True indicates evenness and False indicates oddness.
Another approach that does not use the multiplication, modulo, and division operators would be to use the bitwise operator &. This an esoteric approach because we are dealing with bits. In short, only odd numbers will have their lowest-order bit to be set. So if we do k & 1, we will be able to get the lowest-order bit of number k. We indicate the lowest-order bit to be set if it is 1. However, if the lowest-order bit is 0, then that means that the number is even. An example would be clearer:
Remarks:
- The % is a modulo operator, which returns the remainder that occurs from the division of m / n.
- By divisibility, a number divided by another number must not leave a remainder.
- The & is a bitwise operator, which returns the result of performing AND on each bit of the first operand and the second operand. For example, if the first bit of the first operand was a 1 and the first bit of the second operand was 1, then the result's first bit would be 0. These operands must be of type integer for it to work. A background in Computer Architecture would be helpful in understanding why bitwise operators exist and how they work.
- Many sources say that the bitwise approach is more efficient (which I do agree), but it is not intuitive if one does not understand how bits and bitwise operators work.
Comments
Post a Comment