Designing Different Algorithms

We need to help a lemonade stand owner in providing the required quantity of lemonade as per the customer’s will. He has two containers with $5$-liter and $8$-liter capacity, but there is no measurement mark on either of the containers. To provide 5 or 8 liters of lemonade to customers, it would be very straightforward. But if a customer demands either $1, 2, 3, 4, 6, or \space 7$, then what should the methodology be?

Solution

We can fill either container with lemonade and then pour it into the other one to get the desired quantity.

1 liter

• First of all, we need to fill the $8l$ container and pour that into the smaller one with $5l$ capacity. As a result, only $3$ liters will be left in the $8l$ container.
• Empty the $5l$ container and pour the remaining $3$ liters from the $8l$ container into it.
• Now, fill the $8l$ container again, and pour that into the smaller one that already contains $3$ liters. As a result, $6$ liters will be left in an $8l$ container.
• We have to empty the $5l$ container and pour the $8l$ container, which already has $6$ liters, into it. This procedure will leave $1$ liter lemonade in the $8l$ container. We can give it to the customer.

2 liters

• Fill the $5l$ container and pour it into the larger container with $8l$ capacity. Now $3$ more liters can be added to the larger container.
• Fill the $5l$ container again and pout into the $8l$ container where the available empty capacity is $5$ liters. As result, $2$ liters will be left in a $5l$ container, which can be forwarded to the customer.

Binary number system

It’s a number system with base $2$ as it only contains two alphabets, $1$ and $0$, to represent any number.

The binary number system starts with $0$, and the next number can be obtained by adding $1$ to it. So, the 2nd number will be $1$. For the next number, $(1+1 = 10)_2$, we keep $0$ to the right and carry $1$ to the left. And so on.

Remember: In computers, a binary number system is used where we can switch off the transistor (case-0) or switch on the transistor (case-1) by providing the required voltages.

Application of binary number system

We need to create and print money bills of any amount between $\$1$ and $\$50$ in order to create a currency system that can provide change for any transaction within this range, and it should have the least effect on the environment.

Solution 1

Any transaction can be processed by creating $50$ money bills of $\$1$ each.

But there is a drawback – the more money bills we print, the higher percentage of trees will be utilized. Hence, it is not an environment-friendly solution.

Solution 2

If we create $24$ money bills of $\$2$ each and $2$ money bills of $\$1$ each, we can achieve our goal. In this manner, we have saved approximately $50$ of the trees.

Solution 3

• A $\$1$ bill is mandatory because it’s the minimum and we cannot leave this.
• Moving towards $\$2$, let’s add this to our money bills list too.
• We can skip $\$3$ as with the combination of $\$1$ and $\$2$, we can get $3 so no need to print $\$3$ bill.
• We will be needing $\$4$ and after that, until $\$7$, we won’t be needing any extra money bill as with the combination of $\$1$, $\$2$ and $\$4$ we can manage the range $1-7$.
• Now we will add $\$8$ to our bills which will allow us to perform any transaction from $\$1$ to $\$15$.
• Similarly, we need to have a $\$16$ bill in order to widen our range to $\$1$ to $\$31$.
• So we have the following money bills: $\$1$, $\$2$, $\$4$, $\$8$ and $\$16$. But we cannot add $\$32$ as this will exceed our limit of $\$50$. As we can now do any transaction from $\$1$ to $\$31$ and the remaining amount is $50-31=19$. Therefore, we’ll have the last bill worth $\$19$. Now the question is how to pay the amount from $32 ... 50$. We know any quantity less than or equal to $31$ can be easily paid through $\$[1,2,4,8,16]$. For any amount $A$ greater than $31$, we will first pay through the $\$19$ bag, then the remaining amount ($A-19$) will be within the range of $1...31$, which we already know how to pay through the other bags. E.g. if we want to pay $\$40$ the solution will be $19+16+4+1=40$.

In this fashion, we can do transactions within our complete given range, and we have saved the trees as much as possible.

The final list of money bills will be $\$[1, 2, 4, 8, 16, 19]$.
This pattern is similar to our binary number system where each bit added to the right doubles the range.

Exercise

Suppose we have two strings that only have one known property – when lit at either end, it takes only $1$ hour to burn either of them. The rate at which the strings burn is random, and each string is different (hence if we break the string into two halves it may be the case that both strings have different burning durations). How can we measure $1.5$ hours and $45$ minutes?

Directions to look at the problem

To measure $1.5$ hours, first, we burn a string from one end, and when it is completely burned, an hour has passed. After that, we have to burn the second string from both ends simultaneously. Once it is completely burned, $0.5$ hours have passed. So, a total of $1.5$ hours have been measured.

For $45$ minutes, a similar strategy needs to be implemented.