Least Operators to Express Number - Practice Coding Problems

Least Operators to Express Number - Problem

Given a single positive integer x, we will write an expression of the form x (op1) x (op2) x (op3) x ... where each operator op1, op2, etc. is either addition, subtraction, multiplication, or division (+, -, *, or /).

For example, with x = 3, we might write 3 * 3 / 3 + 3 - 3 which is a value of 3.

When writing such an expression, we adhere to the following conventions:

The division operator (/) returns rational numbers.
There are no parentheses placed anywhere.
We use the usual order of operations: multiplication and division happen before addition and subtraction.
It is not allowed to use the unary negation operator (-). For example, x - x is a valid expression as it only uses subtraction, but -x + x is not because it uses negation.

We would like to write an expression with the least number of operators such that the expression equals the given target. Return the least number of operators used.

Input & Output

Example 1 — Small Target

$ Input: x = 3, target = 19

› Output: 5

💡 Note: We can write 19 as 3*3*3 - 3 - 3 - 3 + 3/3, which uses 5 operators: 3 multiplications + 2 subtractions = 5 total operators

Example 2 — Simple Case

$ Input: x = 5, target = 501

› Output: 8

💡 Note: 501 can be expressed as 5*5*5*4 + 1, where 4 = 5-1 and 1 = 5/5, requiring 8 operators total

Example 3 — Edge Case

$ Input: x = 100, target = 100

› Output: 1

💡 Note: Target equals x, so we just need 1 occurrence of x with 0 operators between

Constraints

2 ≤ x ≤ 100
1 ≤ target ≤ 2 × 10⁸

Visualization

Tap to expand

Understanding the Visualization

Input

Given x=3 and target=19, find minimum operators

Process

Express 19 using powers of 3 with +, -, *, / operators

Output

Return minimum operators needed: 5

Key Takeaway

🎯 Key Insight: Express the target as a combination of powers of x, choosing between positive and negative contributions to minimize total operators

Asked in

G Google 15 f Facebook 12 M Microsoft 8

The key insight is to treat this as a base conversion problem where we express the target using powers of x with minimal operators. The optimal approach uses mathematical decomposition to build the target efficiently by considering both positive and negative contributions. Time: O(log(target)), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(4^n)	O(n)	Try all possible expressions recursively without optimization
Optimized Mathematical Approach	O(log(target))	O(1)	Use mathematical properties to build target efficiently with positive and negative contributions
Memoized Recursion	O(log²(target))	O(log(target))	Use dynamic programming with memoization to avoid recalculating subproblems

Brute Force Recursion — Algorithm Steps

Start with base case: if target equals x^k for some k, return k operators
Try adding/subtracting different powers of x
Recursively solve for remaining target
Return minimum operators found

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with target and explore all operator choices

Branch

Try +, -, *, / at each position recursively

Count

Track minimum operators needed

Code -

solution.c — C

#include <stdio.h>
#include <math.h>
#include <limits.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int solve(int x, int target, int cur, int i) {
    if (i >= 32) return INT_MAX / 2;
    if (cur == target) return 0;
    
    int ans = INT_MAX / 2;
    int k = i == 0 ? 1 : (int)pow(x, i);
    
    // Add k
    if (cur + k <= target + k) {
        ans = min(ans, i + solve(x, target, cur + k, i + 1));
    }
    
    // Subtract k
    if (cur - k >= target - k) {
        ans = min(ans, i + solve(x, target, cur - k, i + 1));
    }
    
    // Try next power
    ans = min(ans, solve(x, target, cur, i + 1));
    
    return ans;
}

int solution(int x, int target) {
    if (target == x) return 0;
    return solve(x, target, 0, 0);
}

int main() {
    int x, target;
    scanf("%d %d", &x, &target);
    printf("%d\n", solution(x, target));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(4^n)

Each position can have 4 operators, creating exponential branches

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth proportional to expression length

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~35 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler