# Make a sequence an increasing sequence by adding a number multiple times

#### Tags: algorithm, java

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 = 3 & a = 3, so increment a by B so a = 3+2 = 5

Now a = 5 & a=2, so incremease a by multiple of B so it is more than a, so a = 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);
}
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`.

Source: stackoverflow