Matchstick problem: PUZZLE

Can someone tell me how to solve this problem?
alt text

i.e, for numbers like:-

0 = 6 matchsticks
1 = 2 matchsticks
2 = 5 matchsticks
3 = 5 matchsticks
4 = 4 matchsticks
5 = 5 matchsticks
6 = 6 matchsticks
7 = 3 matchsticks
8 = 7 matchsticks
9 = 5 matchsticks


An integer which denotes the total matchsticks that are available at a time.


Total digital numbers that can be formed with a given matchsticks.


Input: 5

Output: 10


Total digital numbers can be obtained are:- 1,2,3,4,5,7,9,11,17,71

Find the number of arrangements for all 0<=j<=i-1 matchsticks, you can use these to find the number of arrangements for the first ‘i’ matchsticks, store these values in an array A[], your answer will be A[N]. Suppose that you want to find the answer for position ‘i’, we will go through all the possibilities for the rightmost digit in the arrangement, and then we will count the number of ways in which we can do that. Let’s suppose that you decide that the last digit will be ‘8’, so you will be needing 7 matchsticks for it, and your answer in that case will be A[i-7].

This is because all different arrangements of the first i-7 numbers, followed by the digit ‘8’ that you’re forming with the last 7 matchsticks will give you new arrangements. So, in this way, you will sum up the new arrangements for all possible digits. So, for any ‘i’, your answer will be given by:

A[i]=A[i-6]+A[i-2]+A[i-5]+A[i-5]+A[i-4]+A[i-5]+A[i-3]+A[i-7]+A[i-5], each term in this summation represents a different choice for the rightmost digit in the number that you will be forming. The complexity of this solution is O(N), and I think it can be improved if you use matrix exponentiation. Let me know (comment) if anything isn’t clear.

You are saying that, I have to calculate all the matchsticks of all digital numbers by our-self. Isn’t it?

Well If yes, then wouldn’t it be cumbersome or tricky method?

I’m sorry, I don’t understand what you’re saying

1 Like

Please elucidate your first and second paragraph with appropriate example if you can!

can you please elaborate it more with some examples , it will be great to understand it . @hemanth_1