2
\$\begingroup\$

Recently I've been doing some challenges on HackerRank and came across this one. First, I tried with Python, and then C. Both of my codes failed due to timeout restrictions.

It would be very helpful, if someone can tell me what can be improved in (one of) my codes (performance-wise).

Challenge description:

Alice purchased an array of \$n\$ wooden boxes that she indexed from \$0\$ to \$n - 1\$. On each box \$i\$, she writes an integer that we'll refer to as \$box_{i}\$.

Alice wants you to perform \$q\$ operations on the array of boxes. Each operation is in one of the following forms:

(Note: For each type of operations, \$l \le i \le r\$)

  • 1 l r c: Add \$c\$ to each \$box_{i}\$. Note that \$c\$ can be negative.
  • 2 l r d: Replace each \$box_{i}\$ with \$\left\lfloor\frac{box_{i}}{d}\right\rfloor\$.
  • 3 l r: Print the minimum value of any \$box_{i}\$.
  • 4 l r: Print the sum of all \$box_{i}\$.

Recall that \$\lfloor x \rfloor\$ is the maximum integer \$y\$ such that \$ y \le x\$ (e.g., \$\lfloor -2.5\rfloor = -3\$ and \$\lfloor -7\rfloor = -7\$).

Given \$n\$, the value of each \$box_{i}\$, and \$q\$ operations, can you perform all the operations efficiently?

Input format

The first line contains two space-separated integers denoting the respective values of \$n\$ (the number of boxes) and \$q\$ (the number of operations).

The second line contains \$n\$ space-separated integers describing the respective values of \$box_0, box_1, \dots, box_{n-1}\$ (i.e. the integers written on each box).

Each of the \$q\$ subsequent lines describes an operation in one of the four formats described above.

Constraints

  • \$1 \le n,q \le 10^5\$
  • \$-10^9 \le box_{i} \le 10^9\$
  • \$0 \le l \le r \le n - 1\$
  • \$-10^4 \le c \le 10^4\$
  • \$2 \le d \le 10^9\$

Output Format

For each operation of type \$3\$ or type \$4\$, print the answer on a new line.

Sample Input 0

10 10
-5 -4 -3 -2 -1 0 1 2 3 4
1 0 4 1
1 5 9 1
2 0 9 3
3 0 9
4 0 9
3 0 1
4 2 3
3 4 5
4 6 7
3 8 9

Sample Output 0

-2
-2
-2
-2
0
1
1

Explanation 0

Initially, the array of boxes looks like this:

[ -5 ][ -4 ][ -3 ][ -2 ][ -1 ][ 0 ][ 1 ][ 2 ][ 3 ][ 4 ]

We perform the following sequence of operations on the array of boxes:

  1. The first operation is 1 0 4 1, so we add \$1\$ to each \$box_{i}\$ where \$0 \le i \le 4\$:

[ -4 ][ -3 ][ -2 ][ -1 ][ 0 ][ 0 ][ 1 ][ 2 ][ 3 ][ 4 ]

  1. The second operation is 1 5 9 1, so we add \$c = 1\$ to each \$box_i\$ where \$5 \le i \le 9\$.

[ -4 ][ -3 ][ -2 ][ -1 ][ 0 ][ 1 ][ 2 ][ 3 ][ 4 ][ 5 ]

  1. The third operation is 2 0 9 3, so we divide each \$box_i\$ where \$0 \le i \le 9\$ by \$d = 3\$ and take the floor:

[ -2 ][ -1 ][ -1 ][ -1 ][ 0 ][ 0 ][ 0 ][ 1 ][ 1 ][ 1 ]

  1. The fourth operation is 3 0 9, so we print the minimum value of \$box_i\$ for \$0 \le i \le 9\$. $$min(-2, -1, -1, -1, 0, 0, 0, 1, 0, 1) = -2$$
  2. The fifth operation is 4 0 9, so we print the sum of \$box_i\$ for \$0 \le i \le 9\$ which is the result of $$ -2 + -1 + -1 + -1 + 0 + 0 + 0 + 1 + 1 + 1 = -2$$ ... and so on.

C code:

int minBox(int *box, int l, int r){
    int min=box[l];
    for(int i = l+1; i<=r; i++)
        if(box[i] < min)
            min = box[i];
    
    return min;
}

int sumBox(int *box, int l, int r){
    int sum=0;
    for(int i = l; i<=r; i++)
        sum += box[i];

    return sum;
}

void operateOnBox(int *op, int *box){
    switch(op[0]){
        case 3:
            printf("%d\n", minBox(box, op[1], op[2]));
            break;

        case 4:
            printf("%d\n", sumBox(box, op[1], op[2]));
            break;

        case 1:
            for(int i = op[1]; i <= op[2]; i++)
                box[i] += op[3];

            break;

        case 2:
            for(int i = op[1]; i <= op[2]; i++)
                box[i] = (int) floor(box[i]/((float)op[3]));

            break;
    }
}

int main()
{

    int n, q, *box;
    scanf("%d %d", &n, &q);

    box = (int*) malloc(sizeof(int) * n);
    for(int i = 0; i<n; i++)
        scanf("%d", box+i);

    for(int i = 0; i<q; i++){
        int op[4];
        scanf("%d %d %d", op, op+1, op+2);

        if(op[0] == 1 || op[0] == 2)
            scanf("%d", op+3);
        
        operateOnBox(op, box);

    }

    return 0;
}

Python 3 code:

def operate(op, box):
    if op[0] == 3:
            print(min(box[op[1]:op[2]+1]))
    elif op[0] == 4:
            print(sum(box[op[1]:op[2]+1]))
    elif op[0] == 1:
            box[op[1]:op[2]+1] = map(lambda x: x+op[3], box[op[1]:op[2]+1])
    elif op[0] == 2:
            box[op[1]:op[2]+1] = map(lambda x: math.floor(x/op[3]), box[op[1]:op[2]+1])



if __name__ == '__main__':
    nq = input().split()

    n = int(nq[0])

    q = int(nq[1])

    box = list(map(int, input().rstrip().split()))

    for i in range(q):
        op = list(map(int, input().split()))
        operate(op, box)
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! Generally it's better to include text rather than an image because text is searchable and the image is not. Also, the text tends to be smaller. \$\endgroup\$ – Edward Jun 25 at 19:00
  • \$\begingroup\$ @Edward Thank you, I tried to paste a very brief description of it, but it contains mathematic formulas that do not render here. I'll keep it in my mind for next questions. \$\endgroup\$ – Jaafarb Jun 25 at 19:04
  • 1
    \$\begingroup\$ Please take a look at how other programming-challenge questions have solved this. \$\endgroup\$ – Mast Jun 25 at 19:07
  • \$\begingroup\$ I've edited the question for you to show how this can be done. Please study it so you know how to do it yourself from here on. \$\endgroup\$ – Edward Jun 25 at 19:43
  • \$\begingroup\$ @Edward I will, thank you. \$\endgroup\$ – Jaafarb Jun 25 at 20:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.