CODEWITHSUNDEEP
algorithmdiscrete-mathematics
TijuanaTaxi
TijuanaTaxi

Reputation: 121

Maximizing expression with only division operator

The problem is that I have to find algorithm that maximizes expression of n integers (they can be negative) only by putting brackets on some places. I can't change the order of numbers.

Example:

for input: 4 6 8 2 5

output should be: 4/(6/8/2/5)

The goal is to put brackets to maximize the result of given expression. In some cases is not necessary to put brackets at all.

Example:

input: 8 -6 3 -2 -4 5 output: 8 / -6 / 3 / -2 / -4 / 5

The output should be maximal value possible!

I had idea of finding all possibilities using recursion, but my solution wasn't approved by professor (he said that there is an easier and faster solution!) and now when my deadline has passed I am looking for direct help!

Upvotes: 2

Views: 142

Answers (1)

Diego Mazzaro
Diego Mazzaro

Reputation: 2882

Maybe it was not a programming test but a math one.

Let's say your input is: a b c d e f ... z

Consider that if you don't put any parenthesis the result can be written as

a^+1 * b^-1 * c^-1 * d^-1 ... z^-1

And when you put any parenthesis pair you get:

  • the first number inside the parenthesis remains with the same exponent
  • all the other inside the parenthesis will get the exponent sign changed

So in the end all your possibilities to influence the results are expressed by the following:

  • a: the exponent will always be +1
  • b: the exponent will always be -1
  • all other: you can choose the exponent that you want with the parenthesis.

So the solution can be as follows:

  • look to the sign of inputs and define the sign of the result (even or odd count of negative numbers)
  • if result has to be positive
    • then your task is to obtain the highest absolute value
    • in this case the solution is a/(b/c/d/....z)
    • this follows by
      • a is fixed at the numerator
      • b is fixed at denominator
      • we divided b the most possible so we're having the lowest possible denominator's absolute value
      • so the result's absolute value will be the highest possible
  • if result has to be negative
    • then your task is to obtain the lowest absolute value
    • in this case the solution is a/b/c/d/....z (no parenthesis)
    • this follows by
      • a is fixed at the numerator
      • we divided a the most possible so we're having the minimum possible absolute value

Maybe now I after this math-work the coding-work can start and the resulting time complexity will be O(n): just count the number of negative inputs and you get the answer!.

Upvotes: 1

Related Questions