How to think about Matchstick problems
The problem statement is something like this :
We will be given a number of matchsticks and we need to find out what is the smallest number we can form from the number.
Here are some conditions to make our life easier.
1. There may be leading zeros in the number
2. Every stick must be used
Let's understand and analyze the problem first :
Firstly let's try to find a pattern. Then it will be easier to implement on code.
From the sticks, we can observe we need at least 2 sticks to form a number. Lets start from there.
If we were given 2 we can form 1(Notice in the matchsticks picture to form 1 it takes two sticks).
If we are given 3 then we could form 7(from the image we can notice 7 takes 3 sticks)
If we were given 4we can form 4((from the image we can notice 4 takes 4 sticks)
If we were given 5 then might run into a problem. Cause if we notice from the 5 sticks we can form 2, 3, and 5. As all of them take 5 sticks and form the statement we can decide that 2 is the smaller. So if we have 5 sticks we can form 2.
If we were given six sticks then we can form 0, 6, and 9 as 0 is the smallest number among them so we can conclude the smallest number we can form is 0.
Moving on if we have 7 sticks we can form 8. With all the sticks. Like this
Great this was the final number in single digits we can form with sticks.
Let's summarize upto this before moving on.
For,
2 sticks → number can be formed 1
3 sticks → number that can be formed is 7
4 sticks → number that can be formed is 4
5 sticks → number that can be formed is 2, 3, 5 → smallest is 2
6 sticks → number that can be formed is 0, 6, 9 → smallest is 0
7 sticks → number that can be formed is 8
Note:
1. With 2, 3, 4, 5, 6, and 7 numbers can be formed.
2. Smallest number 0 can be formed with 6 sticks
Let's move on,
If we were given 8 sticks then we could there are a number of choices we could have.
We can break 8 into the summation of available sticks possible (2, 3, 4, 5, 6, 7)
2 + 2 + 2 + 2 = 8which will form 1111
3 + 5 = 8 which will form 72 or 27
6 + 2 = 8 which will form 01 or 10
Here from the cases, we can decide 01 is the smallest number.
Moving on,
If we were given 9 sticks then we could there are a number of choices we could have.
We can break 9 into the summation of available sticks possible (2, 3, 4, 5, 6, 7)
7 + 2 = 9 which will form 18 or 81
3 + 6= 9 which will form 70 or 07
5 + 2 + 2 which will form 211 or 121 or 112 (By taking 2 as the smallest)
5 + 4 which will form 24 or 42
Here from the cases, we can decide 07 is the smallest number.
If we notice closely the case of 8 and 9. If we have a leading 0 it is becoming the smallest number and the leading 0 is coming from 6 sticks. So we can decide from here we need to form as much as leading 0 we can. To do that we can divide the number by 6 and the result will be the number of zeros.
Like this,
For,
12 → The smallest number will be 00
18 → The smallest number will be 000
24 → The smallest number will be 0000 and so on.
If have numbers that are not divisible with 6 we just take the integer part as a number of leading 0.
For 14 number of leading 0 will be 00(2), For 15, 16, and 17 it will be zero as well and the remainder is 2,3, 4, and 6 accordingly.
So we can form a formula here,
We need to divide the number into two parts one is a multiple of 6 which will produce the highest number of leading 0.
After dividing any number by 6 we can have 0–5 remainder.
We can think of it as,
Suppose we have 60 match sticks we used all of them to produce 10 zeros.
If we have 65 we could use 60 sticks to produce 10 zeros and we would have 5 sticks remaining. And with those 5 sticks, we could form 2. as 2 is the smallest number.
Now let's organize this idea,
First, we need to break the number into two pieces one part will be the multiple of 6. Which will create a leading 0 and another part will be the remainder.
48 → 6 X 8 = 48 + 0
49 → 6 X 8 = 48 + 1
50 → 6 X 8 = 48 + 2
51 → 6 X 8 = 48 + 3
52 → 6 X 8 = 48 + 4
53 → 6 X 8 = 48 + 5
54 → 6 X 9= 54 + 0
55 → 6 X 9= 54 + 1
56 → 6 X 9 = 54 + 2
57 → 6 X 9= 54 + 3
58 → 6 X 9= 54 + 4
59 → 6 X 9= 54 + 5
60 → 6 X 9 = 60 + 0
If we notice we got our pattern to follow. The remainder is from 0 — 5. After diving by 6. We can have 0 – 5 remainder only.
Now let's use the remainder.
If we have remainder as 0 then we don’t need to do anything.
If we have the remainder as 2 then we can form 1 with these two sticks
If we have the remainder as 3 then we can form 7 with these two sticks
If we have the remainder as 4 then we can form 4 with these two sticks
If we have the remainder as 5 then we can form 2 with these two sticks
If we notice the one is missing here only let's solve the last part of the puzzle. If we have one then we can see we don’t have a number that can be formed with this one so that.
As we need to use all the sticks we need to think about it a bit.
As our goal is to use it to produce as much leading 0 we can. So we can form think of it like thinks we will take one six which was producing zero. So the number of sticks now we have is 7(6 + 1)
With the 7 sticks from the previous image, we can see we can produce 8 as a single digit.
Like,
If we have 13 sticks we will have 6 digits for creating one zero and the rest seven digits for 8. So the final output will be 08.
If we have 61. Then will will have 9 x 6 = 54 sticks form creating zero and rest seven for creating 8.
The code implementation in c could be something like this.
Here we are first handling the 1 part then the rest part.