how to shrink an array if two consecutive numbers in an array are equal then remove one and increment other

Question

How to shrink an array if two consecutive numbers in an array are equal then remove one and increment other

Example 1:

int a[6]={2,2,3,4,4,4};

// Output: 6

Example 2:

int b[7]={1,2,2,2,4,2,4};

// Output: {1,3,2,4,2,4}

Answer 1

This can be done in near-linear time like so:

a = [2, 2, 3, 4, 4, 4]
b = [1, 2, 2, 2, 4, 2, 4]
c = [5, 5, 5, 1]

def shrink_array(a):
    res = []
    
    for i in range(1, len(a)+1):
        if i < len(a) and a[i] == a[i-1]: # if equal to previous
            a[i] += 1 # increment and move on
        else:
            if len(res) > 0 and res[-1] == a[i-1]: # if equal to last in res
                res[-1] += 1 # increment last in res
            else:
                res.append(a[i-1]) # add to res

        while len(res) > 1 and res[-1] == res[-2]: # shrink possible duplicates
            res[-2] += 1
            del res[-1]
        
    return(res)

for arr in [a, b, c]:
    print(shrink_array(arr))

Output:

[6]
[1, 3, 2, 4, 2, 4]
[6, 5, 1]

Answer 2

lst = [2,2,3,4,4,4]
    
def shrink(lst):
    idx = 0
    while len(lst) > idx+1:
        a, b = lst.pop(idx), lst.pop(idx)

        if a == b:
            lst.insert(idx, a+1)
            idx = 0
        else:
            lst.insert(idx, b)
            lst.insert(idx, a)
            idx += 1

shrink(lst)
print(lst)

Prints:

[6]

---

For [5, 5, 5, 1] prints [6, 5, 1]