By Chandrahas M. Halai
After a few hours of getting a new mobile phone number I forgot it. In India, we have ten digit mobile phone numbers. Fortunately, I had paid premium amount to get a special number. In this special number, the first digit (from left to right) is equal to number of zeroes in that number, the second digit is equal to the number of ones in that number, third digit is equal to the number of twos in that number and so on and so forth. For example, if first digit of number is 4 then there are four zeroes in that number. There is only one such ten-digit number. So, what is my mobile phone number?
Solution:
There are ten-billion ten-digit numbers from 0000000000 to 9999999999. Finding that one unique number amongst ten-billion is like finding a needle in a haystack.
We can develop an algorithm that constructs the number using the specified conditions.
| An algorithm is a step-by-step procedure to solve a given problem. |
We can begin solving the problem with a clean slate, i.e.
00000 00000
(I am breaking the number into two groups of five digits for better readability.)
Here we have ten zeroes. Hence, as per given conditions we should put a 10 in the first digit. Firstly 10 is not a digit and secondly putting any digit other than zero in the place of first digit will alter our count of zeroes in the number. The number of zeroes will be decreased by one, that is, now the number of zeroes will now be 9. Let us now put 9 in the first digit.
Hence, now our number will be
90000 00000
Our algorithm will work on this number to arrive at the required number. We begin by checking every digit in the number to ensure that it contains the right count of the corresponding digits. If not, then the right count is put in that particular place.
First pass or First Iteration:
(You will understand later why I am calling this step the First pass / iteration)
Checking the First digit:
This digit should have the count of zeroes in the number.
We see that it contains 9 and when we count the number of zeroes we see that it is also 9. Hence no change is made to the number. The number will be:
90000 00000
The digits from second to the ninth all contain zeroes and they are correct.
Checking the Tenth or the Last digit:
This digit should have the count of 9s in the number.
We see that there is one 9 in the number. Hence, we put a 1 in that place. Thus, our number becomes:
90000 00001
Have we got the desired ten-digit number? Let us check every digit of the number once again.
Second pass or Iteration:
Checking the First digit:
At present this place contains a 9. Let us count the number of zeroes in the number. We see that there are eight zeroes instead of 9. Hence, we will replace the 9 with 8. Thus, the number becomes:
80000 00001
Checking the Second digit:
This digit should have the count of 1s in the number. At present it contains a 0. Let us count the number of 1s in the number. We see that there is one 1 (in the last digit). Hence, we will put a 1 in that place. Thus, the number becomes:
81000 00001
The digits from third to the Eighth all contain zeroes and they are correct.
Checking the Ninth digit:
This digit should have the count of 8s in the number. At present it contains a 0. Let us count the number of 8s in the number. We see that there is one 8 (in the first digit). Hence, we will put a 1 in that place. Thus, the number becomes:
81000 00011
Checking the Tenth or the Last digit:
This digit should have the count of 9s in the number.
At present that place contains a 1. Let us count the number of 9s in the number. We find that there are no 9s in the number. Hence, we put a 0 in that place. Thus, our number becomes:
81000 00010
Have we got the desired ten-digit number? Let us check every digit of the number once again. We are going to repeat the same steps (procedure) once again. We are going into a loop or iteration (iteration means repetition). When we find that all the digits contain the right count, we come out of the loop.
Third pass or Iteration:
Checking the First digit:
At present this place contains an 8. Let us count the number of zeroes in the number. We see that there are seven zeroes instead of 8. Hence, we will replace the 8 with 7. Thus, the number becomes:
71000 00010
Checking the Second digit:
At present this place contains a 1. Let us count the number of 1s in the number. We see that there are two 1s instead of one. Hence, we will replace the 1 with 2. Thus, the number becomes:
72000 00010
Checking the Third digit:
At present it contains a 0. Let us count the number of 2s in the number. We see that there is one 2. Hence, we will put a 1 in that place. Thus, the number becomes:
72100 00010
The digits from fourth to the seventh all contain zeroes and they are correct.
Checking the Eighth digit:
At present it contains a 0. Let us count the number of 7s in the number. We see that there is one 7 (in the first digit). Hence, we will put a 1 in that place. Thus, the number becomes:
72100 00110
Checking the Ninth digit:
At present that place contains a 1. Let us count the number of 8s in the number. We find that there are no 8s in the number. Hence, we put a 0 in that place. Thus, our number becomes:
72100 00100
The last digit contains a zero and that is correct. Hence there will be no change in the number.
Have we got the desired ten-digit number? Let us check every digit of the number once again.
Fourth pass or Iteration:
Checking the First digit:
At present this place contains a 7. Let us count the number of zeroes in the number. We see that there are six zeroes instead of 7. Hence, we will replace the 7 with 6. Thus, the number becomes:
62100 00100
The second and third digits contain a 2 and a 1 respectively and both are found to be correct.
The digits from fourth to the sixth all contain zeroes and they are correct.
Checking the Seventh digit:
At present this place contains a 0. Let us count the number of 6s in the number. We see that there is one 6 (in the first digit). Hence, we will put a 1 in that place. Thus, the number becomes:
62100 01100
Checking the Eighth digit:
At present that place contains a 1. Let us count the number of 7s in the number. We find that there are no 7s in the number. Hence, we put a 0 in that place. Thus, our number becomes:
62100 01000
The ninth and the last digits both contain a zero and that is correct. Hence there will be no change in the number.
Have we got the desired ten-digit number? Let us check every digit of the number once again.
Fifth pass or Iteration:
In this pass we find that all the digits are correct. No changes are made to the number in this pass. This means that we have got our desired mobile phone number.
Thus the mobile phone number is 62100 01000.
You can use this algorithm to program a computer to find this unique number. Developing algorithms and coding them into programs so that computers can solve problems is one of the most significant part of computer science.
To get the mobile number we had applied the algorithm on the number 90000 00000. Instead of applying the algorithm on this, we can use any random ten-digit number and still get the correct answer.
chandrahas blogs 