OperationsArrangement | Topcoder Archive

Problem Statement

You are given a sequence of digits. You must insert either a '+' (addition) operator or a '*' (multiplication) operator between each pair of adjacent digits in such a way that minimizes the value of the resulting expression. The expression should be evaluated using the standard order of operations (multiplication has a higher precedence than addition).

You will be given a String sequence. Perform the procedure described above on the sequence and return the resulting expression. If there are several possible answers, return the one that comes first lexicographically. Note that '*' comes before '+' lexicographically.

Definition

Class:: OperationsArrangement
Method:: arrange
Parameters:: String
Returns:: String
Method signature:: String arrange(String sequence)
(be sure your method is public)

Constraints

sequence will contain between 2 and 50 characters, inclusive.
Each character in sequence will be a digit ('0'-'9').

Examples

```
"222"
```
```
Returns: "2*2+2"
```
The minimal result can be obtained in three ways: "2*2+2", "2+2*2" and "2+2+2". The first one comes first lexicographically.
```
"322"
```
```
Returns: "3+2*2"
```
```
"307"
```
```
Returns: "3*0*7"
```
```
"391118571"
```
```
Returns: "3+9*1*1*1+8+5+7*1"
```

"111221911212"

Returns: "1*1*1*2*2*1+9*1*1+2*1*2"

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.