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

Question

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?

Daniel · Accepted Answer · 2020-04-30 23:50:43Z

3

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 Bs you need to add, which is the difference divided by B.

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

edited Apr 30, 2020 at 23:50

answered Apr 30, 2020 at 22:26

Daniel

7,80010 gold badges37 silver badges108 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Marek Over a year ago

Shouldn't it be if(a[i] == a[i - 1]) instead of else if(dif == 0) in order to achieve strictly increasing sequences? Consider the example int[] a = { 1, 3, 3, 2 } and int B = 1: Your code is producing the sequence 1 3 4 4 (3) while the OP's code is producing 1 3 4 5 (4).

Daniel Over a year ago

Yes, in fact there was this problem. I fixed it. The dif thing was not the main issue.

Collectives™ on Stack Overflow

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

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related