Each set of numbers has 4^3 = 64 possible sets of 3 operators. Each set of operators has at most 3! = 6 ways to resolve precedence. Many of these lead to the same result, but it doesn't matter.
With only 384 possibilities to check, I think you can just brute force it. On Sunday, April 1, 2012, doom731 wrote: > Problem is as : > > You received a transmission containing an expression of single digit > positive integers (say: 9 *(5 – 4) * 3). However, during transmission > all operators and brackets were lost and you only received 9 5 4 3. > Given the array of digits, you have to calculate the least positive > integer value of the expression that could NOT have been received by > you. The binary operators possible are *, +, -, / and brackets > possible are ( and ). Note that / is an integer division i.e. 9/5 = > 1. > > Example: You have received 6,6,4,4. The minimum positive integer that > could NOT have been formed is 18. This is because integers less than > 18 are formed as below. > > 1 = 6 /6 + 4-4 > > 2 = 6/6 + 4/4 > > 3 = 6 +( 6/4) -4 > > 4 = (6+6+4) / 4 > > …….. > > 18 cannot be formed > > Input Format: > > FIrst line contains an integer N, the number of digits in the array. > > Then follow N lines each containing a digit. > > Output Format: > > Print a single integer which is the required answer. > > Sample Input: > > 4 > > 6 > > 6 > > 4 > > 4 > > Sample Output: > > 18 > > Constraints: > > 1 <= N <= 10 > > Note: You need not worry about the precedence of operators as you can > impose necessary precedence using brackets at appropriate places. > > > ================================================================================== > > I thought backtracking as an approach , but it will be a mess > considering bracket-permutaions with operands. > > Can you suggest a better approach. > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To post to this group, send email to > [email protected]<javascript:;> > . > To unsubscribe from this group, send email to > [email protected] <javascript:;>. > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. > > -- Paul Smith [email protected] -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
