Least Operator to Express Number in Java
In this article, we will learn about how to obtain a target number using a single number or a single integer by leveraging least operators in Java. There can be many expressions that can bring out the target number but the expression with least or the minimum operators need to be found.
We must construct an equation or formula that comprises only the digit D and that evaluates to the number N given an integer N and the digit D. The operators +, -, *, or / may be used in expressions. Find the least number of operators that satisfy the requirement that D only exist in the expression 10(limit) times or less. Limit the N values as a result. Although how much further you want to go determines the value of limit. However, the below approach may take longer if the limit is large. Keep in mind that there may be more than just one minimal expression of D that equals N, however the expression with fewest operators must be chosen.
Let us understand more clearly with the examples.
Example 1
N = 7, D = 3
3/3+ 3 + 3
Interpretation: 3/3 = 1, and 1+3+3 = 7
The least operators required are 3.
Example 2
N = 501, D = 5
Interpretation: 5 * 5 * 5 * 5 - 5 * 5 * 5 + 5 / 5.
The least operators required are 8.
Example 3
N = 7, D =4
Interpretation: (4+4+4)/4 +4
The least operators required are 4.
Let us understand it with a program.
File name : Solution.java
class Solution {
Map<Integer, Integer> memo = new HashMap<>();
public int leastOpsExpressTarget(int x, int target) {
if (target == 1)
return x == 1 ? 0 : 1;
if (memo.containsKey(target))
return memo.get(target);
long product = x;
int count = 0;
while (product < target) {
count++;
product *= x;
}
// candidate1 : in the form : x*x*...*x - (......) = target
int cand1 = Integer.MAX_VALUE;
if (product == target)
cand1 = count;
else if (product - target < target)
cand1 = count + leastOpsExpressTarget(x, (int)(product - target)) + 1;
// candidate2 : in the form : x*x*...*x + (......) = target
int cand2 = Integer.MAX_VALUE;
product /= x;
cand2 = leastOpsExpressTarget(x, (int)(target - product)) + (count == 0 ? 2 : count);
int res = Math.min(cand1, cand2);
memo.put(target, res);
return res;
}
}
The above is the approach or the algorithm in Java, that can obtain the least count of operators as output.
Input
N = 501, D =5
Output
The expression contains 8 operations.
Input
N = 19, D = 3
Output
The expression contains 5 operations.
The Approach
Divided by (/), rational numbers are returned. There isn’t any parenthesis anywhere in the text. We follow the standard order of operations, with addition and subtraction coming after multiplication and division. Use of the unary negation operator is prohibited (-). For instance, "-x + x" is not a valid expression since it involves negation, but "x - x" is because it just uses subtraction. In order to create an expression that equals the specified target, we want to use the fewest possible operators. Give the least number of operators.
We employ a backtracking strategy. Starting with the provided Digit D, we multiply, add, subtract, add, and divide as much as we can. This method is continued until the sum equals N or until we arrive at the conclusion and turn around to begin a new path. We locate the recursive tree's lowest level in order to determine the smallest expression. utilize the backtracking algorithm after that. Then the program makes the count of the number of operators employed to bring out the desired output.
Note: If there exist expressions with same number of operators in them, anyone will be chosen among them. Both the expressions are valid.
Every level has four additional recursions (at-most). We may therefore claim that the approach has a temporal complexity of 4n, where n represents the number of levels in the recursion trees. Alternatively, we can specify the maximum number of times D should appear in the expression, in this example 10, which is ten.