"Ease the Array" challenge

Question

I'm working on this challenge:

Given an array of integers of size N. Assume ‘0’ as invalid number and all other as valid number. Write a program that modifies the array in such a way that if next number is valid number and is same as current number, double the current number value and replace the next number with 0. After the modification, rearrange the array such that all 0’s are shifted to the end and the sequence of the valid number or new doubled number is maintained as in the original array.

Examples:

Input : arr[] = {2, 2, 0, 4, 0, 8}
Output : 4 4 8 0 0 0

Input : arr[] = {0, 2, 2, 2, 0, 6, 6, 0, 0, 8}
Output :  4 2 12 8 0 0 0 0 0 0

Input:

The first line of the input contains an integer T, denoting the number of test cases. Then T test case follows. First line of each test contains an integer N denoting the size of the array. Then next line contains N space separated integers denoting the elements of the array.

Output:

For each test case print space separated elements of the new modified array on a new line.

Constraints:

1 ≤ T ≤ 10³

1 ≤ N ≤ 10⁵

Example:

Input:

2
5
2 2 0 4 4
5
0 1 2 2 0

Output:

4 8 0 0 0
1 4 0 0 0

I managed to get my code to work for the given input and output cases. However, when I submit it, I get a "time limit exceeded" message.

#include <stdio.h>

int main() {
    //code
    int x,q,n,i,j,k,m,arr[100000],d,t;
    scanf("%d",&x);
    for(q=0;q<x;q++)
    {
        scanf("%d",&n);
        for(t=0;t<n;t++)
        {
            scanf("%d",&arr[t]);
        }
        for(i=0;i<n;i++)
        {
            if(i>0)
            {
                if(arr[i]==arr[i-1])
                {
                    arr[i-1]=arr[i]+arr[i-1];
                    arr[i]=0;
                }
            }
        }
        j=n-1;
        k=0;
        while(k != j)
        {
            if(arr[k]==0)
            {


                for(m=0;k+m+1<=j;m++)
                {
                    arr[k+m]=arr[k+m+1];
                }
                arr[j]=0;
               j--;


            }
            else
            {
                k++;
            }
        }
        for(d=0;d<n;d++)
        {
            printf("%d",arr[d]);

            printf(" ");
        }
        printf("\n");

    }
    return 0;
}

Answer 1

This is a decent start. Here are some things that could be improved.

Naming

Your variable names are single letters that as far as I can tell have no relationship to what they represent. The variable x is the number of test cases to run. You should name it numTestCases or testCases. q is the specific test case you're currently running, so testCase or testCaseIndex would be a better name. n is the number of inputs to read, so numInputs would be a good name. And arr tells us very little other than that it is an array. How about inputs? I would rename i to inputIndex, as it's for iterating over the inputs. d could be outputIndex.

Functions

There are 4 different things your code does:

1. Reads the inputs from the user (or stdin)
2. Finds duplicate items in the array and combines them
3. Moves 0s to the end of the array
4. Prints the results

Each of those should be a different function with a clear name.

Space Efficiency

You have an array declared as int arr[100000]. Assuming a typical 32-bit int implementation, that's ~400k. On my system, the default stack size is 1MB. That means that single array takes up half the stack. If had just two more of those, you'd get a stack overflow just running the app. Since it's only 1 allocation at the start of the program and not a repeating allocation, I recommend using malloc() to allocate the array and freeing it after you've finished.

Time Efficiency

The main slowdown in your code is the part that copies the remaining elements when you find a 0 in the array. There are built-in functions in the standard library to do this task for you. In this case, this loop:

            for(m=0;k+m+1<=j;m++)
            {
                arr[k+m]=arr[k+m+1];
            }

can be replaced with a single line:

            memmove(&arr[k], &arr[k+1], sizeof(arr[0]) * (j - (k + 1) + 1));

This is significantly more efficient. The library function (which is sometimes not even a function), can use SIMD instructions, and other speedups to make it much faster than you're likely to do on your own. And it's portable. When I run the test with just that single change, it passes.

There are other ways you could speed this up, too. Instead of copying the remaining portion of the array at every 0, you could read up to the first 0. Mark that index. Read up to the next 0. Move only the values between those 2 indexes back, and repeat. This way you never move any element in the array more than once.

Answer 2

Although the problem is described in terms of separate steps (modify array, reorder it), we don't actually have to perform exactly those steps, provided we print the correct result.

A more efficient way to process the array is to maintain an input pointer and an output pointer (or indexes - the logic is equivalent), and a simple count of the trailing zeros (which we can just compute, as the output array must be the same length as the input array).

Then, for each element in the input array:

• if it's zero, skip it (and don't advance the output pointer)
• if differs from the the following element, copy it to output unchanged
• else double it and copy to the output, then skip the next input value

When you reach the end of the array, fill the remainder of the output with zeros.

It's quite reasonable to re-use the input array as the output, as you'll never overwrite a value you'll subsequently need. In fact, since the algorithm is single-pass, we don't need to store the input in an array at all.

You don't actually need to write zeros to the output array, as you only need to print the right results: if you have n non-zero values in the output array, then print those values, followed by N-n zeros.