I have an array of numbers, now I want to make this as increasing sequence by adding a fixed number `b`

. I want to find how many times the fixed number `b`

is added to make my array as increasing sequence.

Here is the program which is working:

int process(int[] a, int b) { int count = 0; for (int i = 0; i + 1 < a.length; i++) { int current = a[i]; int next = a[i + 1]; // add b to next element if it is less than current while (next <= current) { next += b; count++; } a[i + 1] = next; } return count; }

**Example:**

int[] a = { 1, 3, 3, 2 }; int B = 2; Output is 3

**Explanation:**

a[1] = 3 & a[2] = 3, so increment a[2] by B so a[2] = 3+2 = 5

Now a[2] = 5 & a[3]=2, so incremease a[3] by multiple of B so it is more than a[2], so a[3] = 2 + 2*2 = 6

So we have incremented 3 times, so the output is 3.

**The time complexity of this program is O(N^2), but I was asked to reduce the time complexity of this program further. What is the better approach?**

This should solve the problem in O(n):

int process(int[] a, int b) { int count = 0, dif = 0, add = 0; for (int i = 1; i < a.length; i++) { dif = a[i] - a[i - 1]; if(dif < 0){ dif = Math.abs(dif); add = (dif / b); if(a[i - 1] + (add * b) >= a[i]) add++; a[i] += add * b; count += add; } else if(dif == 0){ a[i] += b; count ++; } } return count; }

The idea is to take the difference between adjacent numbers and evaluate how many `B`

s you need to add, which is the difference divided by `B`

.

If adjacent numbers are equal, just add a single `B`

.

## Recent Comments