How you gonna start with this question?
-
By using 9 numbers which are 1 to 9 you should find the number of ways to get N using multiplication and addition. For example, if 100 is given, you would answer 7. The reason is that there are 7 possible ways. 100 = 12+3×4+5+6+7×8+9 100 = 1+2×3+4+5+67+8+9 100 = 1×2+34+5+6×7+8+9 100 = 12+34+5×6+7+8+9 100 = 1×2×3+4+5+6+7+8×9 100 = 1+2+3+4+5+6+7+8×9 100 = 1×2×3×4+5+6+7×8+9 If this question is given to you, how would you start?
-
By using 9 numbers which are 1 to 9 you should find the number of ways to get N using multiplication and addition. For example, if 100 is given, you would answer 7. The reason is that there are 7 possible ways. 100 = 12+3×4+5+6+7×8+9 100 = 1+2×3+4+5+67+8+9 100 = 1×2+34+5+6×7+8+9 100 = 12+34+5×6+7+8+9 100 = 1×2×3+4+5+6+7+8×9 100 = 1+2+3+4+5+6+7+8×9 100 = 1×2×3×4+5+6+7×8+9 If this question is given to you, how would you start?
I would start to doubt the assignment, or the teacher. This is more like a Code Fight challenge, or a Hackathon activity. Not a programming assignment. There is no way, a beginner (if asked at even a Bachelors level) would be able to create a program, that takes an input (100) and creates a list. Would be much complex, and would take a lot of time.
The shit I complain about It's like there ain't a cloud in the sky and it's raining out - Eminem ~! Firewall !~
-
By using 9 numbers which are 1 to 9 you should find the number of ways to get N using multiplication and addition. For example, if 100 is given, you would answer 7. The reason is that there are 7 possible ways. 100 = 12+3×4+5+6+7×8+9 100 = 1+2×3+4+5+67+8+9 100 = 1×2+34+5+6×7+8+9 100 = 12+34+5×6+7+8+9 100 = 1×2×3+4+5+6+7+8×9 100 = 1+2+3+4+5+6+7+8×9 100 = 1×2×3×4+5+6+7×8+9 If this question is given to you, how would you start?
To start with, I would think about a brute force approach, and narrow it down by adding more rules.
Make your algorithm start with 123456789
In the next iteration, make your algorithm obtain: 12345678*9
Next obtain, 12345678+9
and 1234567*89, 1234567+89, 1234567*8*9, 1234567*8+9,... and so onIf you write an algorithm to fill this series, you can easily see that there are
3^8possibilities! It might look long enough but it actually is not! I took "three" because there are three possible states: 1. No operation, 2. addition, 3. multiplication. And there are 8 ways you can insert the arithmetic symbols, which is always in-between two numbers. Now, though the value3^8 = 6561is very less, computing huge values won't do any good. What other information do we have? There can't be a '-' sign! That's a good clue. Because, now we know for sure that the value can't reduce and computing values such as 12345*6789 can't be always feasible. So, if there is a number in the expression greater than the required number, from your example, if there is a number greater than 100 in the expression, you don't have to compute the expression to know it is not equal. Simply checking for the "greater than" would help. Now, we have made the problem shorter, starting with an inefficient brute force algorithm! Now lets make it even shorter. Did you observe that if the entered number is 100, the first few elements in the series would definitely not hold? Let's create a function,term f(int x) // returns the term, given the term number.
to which if you pass on the term-number you could automatically obtain the element in
O(1)time. I call itO(1)because the moment you convert the base-10 number passed on as an integer to the functionfto a base-3 number, you have your term! Now each digit of the newly obtained number either becomes + or * or "nothing", and with this we may construct our term. Let's now define rules to skip every term containing numbers greater than 100. To do this, lets speculate and find the term that is at the 1000'th place in the series. Depending on whether the series is greater or lesser, move forwards or backwards in the series (if you are willing to find at-least one solution, or switch to brute force if you want to find all the possible answers). This is how I would start with the problem. And I would write a quick code and test my hypothesis, and add on more rules to it -
By using 9 numbers which are 1 to 9 you should find the number of ways to get N using multiplication and addition. For example, if 100 is given, you would answer 7. The reason is that there are 7 possible ways. 100 = 12+3×4+5+6+7×8+9 100 = 1+2×3+4+5+67+8+9 100 = 1×2+34+5+6×7+8+9 100 = 12+34+5×6+7+8+9 100 = 1×2×3+4+5+6+7+8×9 100 = 1+2+3+4+5+6+7+8×9 100 = 1×2×3×4+5+6+7×8+9 If this question is given to you, how would you start?
-
I see that numbers are in order is it allowed to change order ? Like using 100 = 1×2+38+4+5+6×7+9
Patrice “Everything should be made as simple as possible, but no simpler.” Albert Einstein
ppolymorphe wrote:
is it allowed to change order
I'd guess not, or else the original solution would have had more than 7 possibilities. If they can, then the possible solution space is over 300000 times bigger!
"Fairy tales do not tell children the dragons exist. Children already know that dragons exist. Fairy tales tell children the dragons can be killed." - G.K. Chesterton
-
ppolymorphe wrote:
is it allowed to change order
I'd guess not, or else the original solution would have had more than 7 possibilities. If they can, then the possible solution space is over 300000 times bigger!
"Fairy tales do not tell children the dragons exist. Children already know that dragons exist. Fairy tales tell children the dragons can be killed." - G.K. Chesterton
I do not know why order can not be changed. If we change order, mostly we get different result, because multiplication precedes summation. Of course, here are some options as X*1+2+3 or X*3+2+1 and so on. But if we mix multiplication and summation, then results are different. If we will follow standard rules then mentioned X examples are the same option/solution. EDIT I mean X*1+2+3 or X*1+3+2 not mixing multiplication with summation :)
-
I do not know why order can not be changed. If we change order, mostly we get different result, because multiplication precedes summation. Of course, here are some options as X*1+2+3 or X*3+2+1 and so on. But if we mix multiplication and summation, then results are different. If we will follow standard rules then mentioned X examples are the same option/solution. EDIT I mean X*1+2+3 or X*1+3+2 not mixing multiplication with summation :)
The issue comes with the adjacency "operator" where adjacent digits of the input sequence can be interpreted as a multi-digit number. In the original example there was: 100 = 12+34+5×6+7+8+9 where the 1 and 2 were combined into 12 and the 3 and 4 were combined into 34. If the order could be rearranged, then there are more possible multi-digit numbers: 51, 72, 43, etc. This increases the complexity of the problem space and the number of possible solutions.
"Fairy tales do not tell children the dragons exist. Children already know that dragons exist. Fairy tales tell children the dragons can be killed." - G.K. Chesterton