The question I am given is

We are given an array.

In one operation we can replace any element of the array with any two elements that sum to that element. For example: array = {4, 11, 7}. In one operation you can replace array[1] with 5 and 6 which sums to 11. So the array becomes array = {4, 5, 6, 7}

Return the minimum number of steps in which the whole array can be sorted in non-decreasing order. Along with array in sorted order.

For example: array = {3,9,3}

I think the answer will be 9 will be converted to 3,3,3

But I cannot think of a general formula of doing it.

My thoughts on the solution are

Suppose we want to convert number 6 and 9

We use if and else

IF

we see that we divide a number by 2 and take ceiling but it is greater than the number on it's right side(last example in the question) then we keep subtracting that number(3) until we get integer 0.

That is 9 = 3(number on right of 9 in array in last example) - 3 - 3

ELSE

simply do ceiling(num / 2) to get first number and then num - ceil(num / 2) to ger second. 7 will be 4 and 3.

Please can someone think of a general formula for doing it?

CodePudding user response：

You would want to scan from the right to the left. For convenient explanation, let's mark the right-most element x_0, and the left-most x_{n-1} (n can increase as you split a number into two).

If x_{i} > x_{i-1}, you would want to divide x_{i} into ((x_{i} - 1) / x_{i-1}) 1 parts, where / is integer division, as evenly as possible.

So for example:

• If x_{i} = 15, x_{i-1] = 5, divide x_{i} into (15-1)/5 1 = 3 parts: (5, 5, 5).
• If x_{i} = 19, x_{i-1] = 5, divide x_{i} into (19-1)/5 1 = 4 parts: (4, 5, 5, 5).

(To divide a number equally into a non-decreasing sequence would require a bit of calculation, which shouldn't be too difficult.)

Once you know the sequence, it would be straightforward to repeatedly split a number into 2 to produce that sequence.

CodePudding user response：

Edy's way (as I interpret it) in Python:

def solve(xs):
    limit = 10**100
    out = []
    for x in reversed(xs):
        parts = (x - 1) // limit   1
        limit, extra = divmod(x, parts)
        out  = extra * [limit 1]   (parts - extra) * [limit]
    print(len(out) - len(xs), out[::-1])

solve([4, 11, 7])
solve([3, 9, 3])
solve([9, 4, 15, 15, 28, 23, 13])

Output showing steps and result array for the three test cases (Try it online!):

1 [4, 5, 6, 7]
2 [3, 3, 3, 3, 3]
8 [3, 3, 3, 4, 5, 5, 5, 7, 8, 9, 9, 10, 11, 12, 13]

An output illustrating the progress:

[4, 11, 7] = (input)
[4, 11, [7]]
[4, [5, 6], [7]]
[[4], [5, 6], [7]]

[3, 9, 3] = (input)
[3, 9, [3]]
[3, [3, 3, 3], [3]]
[[3], [3, 3, 3], [3]]

[9, 4, 15, 15, 28, 23, 13] = (input)
[9, 4, 15, 15, 28, 23, [13]]
[9, 4, 15, 15, 28, [11, 12], [13]]
[9, 4, 15, 15, [9, 9, 10], [11, 12], [13]]
[9, 4, 15, [7, 8], [9, 9, 10], [11, 12], [13]]
[9, 4, [5, 5, 5], [7, 8], [9, 9, 10], [11, 12], [13]]
[9, [4], [5, 5, 5], [7, 8], [9, 9, 10], [11, 12], [13]]
[[3, 3, 3], [4], [5, 5, 5], [7, 8], [9, 9, 10], [11, 12], [13]]

Code for that (Try it online!):

def solve(xs):
    print(xs, '= (input)')
    limit = 10**100
    for i, x in enumerate(reversed(xs)):
        parts = (x - 1) // limit   1
        limit, extra = divmod(x, parts)
        xs[~i] = (parts - extra) * [limit]   extra * [limit 1]
        print(xs)
    print()

CodePudding user response：

Here is one idea for the problem.

• Traverse from the rightmost element of the array i = N-2 to 0.
• Split the array element into two parts as large as possible and not exceeding the element just at the right and increment the count of
  split.
• Continue this till the values obtained from splitting arr[i] is not less than the minimum value obtained just at its right. Update
  the minimum value obtained in this process.
• Return the total count of split as the answer.