Given a set of digits and operators, form the given number using least number of operations

user_2413211 0
Viewed 494

We were asked the following problem in a test and I'm not sure how to approach it:

Given a set of numbers and a set of operators, find the least number of operations possible to generate the number.

For example:
Input
set of digits: {8, 1, 6, 2, 7}
set of operations: {*, /, -}
number to be generated: 981

Output
number of operations: 2

Explanation: 981 = 16 * 62 - 11 [ 2 operations: * and - ]

Constraints:
all numbers to be used as integers
0 <= each number in set of digits <= 9
possible set of operations: { +, -, *, / } [ the division operation will always return an integer ]
0 <= number to be generated <= 999
it is necessary that while performing the operations, any of the calculated values must not exceed 999 or be negative
the precedence of operations will always be from left to right, BODMAS/PEMDAS won't be followed. For example: 16*6+2*11 will be calculated as: ((16*6) + 2) * 11

Any help in how to approach the solution would be greatly appreciated.

I think the problem can be approached by generating a number closest to the given number and then the difference can be thought of a new problem of number to be generated. Although I don't think that would yield the least number of operations required to form the given number.

Wasn't able to write much code as I'm not sure how to approach the solution.

Thanks in Advance!

dynamic-programming breadth-first-search graph data-structures algorithm
1 Answers

We can view this problem as a graph problem, and solve it using BFS.

First, we try to create all possible numbers from the set of numbers without using any operator, call this base set. This can be easily achieved by decomposing each number into digits and checking all of those digits are belong to the set of numbers.

for (int i = 0; i < 1000; i++){
   if i can be formed by set of numbers {
      add i to base set;
   } 
}

Now, start from each number in the base set as the start vertices, we traverse to the next vertices by applying different operator to the base set

Queue q = base set
int[] distance = new int[1000]; 
while q is not empty{
   int number = q.pop();
   for(int i : base set){
      for(operator : set of operators) {
          int next = number operator i
          if next < 1000 && next >= 0 && next not visited {
              mark next as visited;
              distance[next] = 1 + distance[number];
              q.add(next);
          } 

      }
   }

} 
return distance[target];

Each vertex will be visited once, so the time complexity will be O(n ^ 2 * m) with n is the maximum number of vertices (1000 in this case) and m is the number of operator

user_27417050
Related