Algorithms for Work: Array - Rules and Ideas Part 2

tldr;

Reduce the search range by using all the rules and constraints.

The idea of counting sort extends to hashes.

You can check out the problem at Part 1 here

A little reminder: it's about the balance scale and finding a fake coin out of 16 coins.

I said that 15 times sure do, 8 times can do also: you pick a pair of coins and try it.

Some others are using the binary idea and split it into 2 parts, so we have

First try: 8 vs 8

Second try: 4 vs. 4

Third, try 2 vs. 2 and find out, so it's 3 times.

It's kind of easy, right? How about it's 24 coins now?

If you apply the same idea, it will take you:

1st try: 12 vs 12; 2nd try: 6 vs 6; 3rd try: 3 vs 3;

and the 4th try will be 1 vs. 1 with 1 extra coin on side.

Total: 4 tries (Log2(n))

Do you notice that in the last try, you had 3 coins and split them to 1 vs. 1 and 1 out? You check if the scale leans to the left, right, or balance?

So the scale provide you with three possible case: Left, Right and balance

What happens if I try to find the fake coin in another way?

From 24 coin, split it into 3 groups: 8 + 8 + 8 (1st try)

Take 2 of it to the scale, depending on the case. I know where the fake coin is.

split 8 into: 3 + 3 + 2 (2nd try)

split 3 into 1 + 1 + 1 (3rd try)

I can find the fake coin after 3 tries. Log3(n)

Actually, we just forgot to make use of the balance case to "reduce the search size."

The idea of algorithms is that we want to make use of the rules and constraints to target the answer (reduce the search range or detect the possible solution).

So the above idea is the same, make use of all the cases.

Counting sort:

We have counting sort that uses the same idea here. We want to make use of the index.

The simple problem is: You are a teacher, and you want to count the number of students for all the scores that your students get during each exam. The score ranges from 0 to 10, with only one integer.

In real life, I will just go through all the scores and put them into the boxes for each score from 0 to 10. I saw the 9 put into the 9 box. After that, I can easily check it again and have an answer. When I need to get the list of students getting 0, I just go directly to the 0 box and get them.

In this case, we create an array and make use of both the index and value of it.

For now, index represents the score, and value represents its number.

And the word represent can be changed accordingly to its own use case.

The score can be 8.5, 7.1, or 5.25. We can still make the rules to map the score to an index, for example:

index 615 represent 6,15 score; From the score for example, 7.25, I know that the target index is 725 (multiply by 100)

We are coming up with a new idea here:

Basic: We can get the value from any index given to array.

New idea: We can get the index from any given value (with our rules).

This mapping from a given value to an index can be understood as representing value, and it comes from the HASH function that we made.

And now we come to the field of hash; see you in the next part.