CODEWITHSUNDEEP
arraysalgorithmsortingmath
BINDU ROY
BINDU ROY

Reputation: 29

make array strictly increasing

Suppose we are given a sequence of size n. We have to make this sequence strictly increasing.we can perform an operation any no of times. i.e select any two adjacent elements A(i) and A(i+1) and replace one of them with (A(i)+A(i+1))/2 (a real number, i.e. without rounding). You may also select each pair of adjacent elements and each element to replace in multiple operations, i.e. any number of times.

We have to tell if it is possible to make sequence strictly increasing? Two possibilities are if the size of the array is 2 and 1st element is greater than 2nd .then not possible. and another possibility is if it contains the same elements .then not possible. Is there any other possibility where answer is not possible.

Upvotes: 1

Views: 677

Answers (1)

Shamis
Shamis

Reputation: 2604

Observation 1: If there are two neighboring numbers j, j and i > j, you can't get to the point where i < j without using any other number k. This is the reason why if you have only two numbers in decreasing order, it's not possible to get an increasing sequence.

Observation 2: If there are two numbers i, j and i < j, by repeating jk+1 = (i + jk) enough times, you can get j = i + c, where c is arbitrary small.
Alternatively, you can make the opposite(e.g. enlarging i so that is arbitrary close to j).

Consequence of 2nd Observation: If the first element is smaller than the last element, you can create your sequence:

  • First make all the elements except the first one as close to the last number as necessary. This gives us the sequence of i < j+c1, j+c2 ... j+cx, j where every |c| is close to zero.
  • Now use i to make the increasing sequence: i, (i + j)/2, ((i + j)/2 + j)/2 ... j. Since the c can be arbitrarily small, it won't be significant. If your sequence needs to be long, you might also want to do the steps multiple times for a sequence of i, ((i+j) / 2 + i) / 2, etc.

Consequence of the previous step: As long as there are two numbers in an increasing order, the ordering is possible:

  • Average the smaller of the numbers to the first position.
  • Average the bigger of the numbers to the last position.
  • Apply the previous step.

Consequence of Observation 1: If the numbers are in decreasing or weakly decreasing(non-increasing) order, they can't be reordered to the increasing order by the averaging operations.

Upvotes: 2

Related Questions