CODEWITHSUNDEEP
javaalgorithm
Learner
Learner

Reputation: 21425

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

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?

Upvotes: 2

Views: 645

Answers (1)

Daniel
Daniel

Reputation: 7714

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.

Upvotes: 3

Related Questions