HackerRank challenge: Box Operations

Question

Recently I've been doing some challenges on HackerRank and came across this one. First, I tried with Python and then with 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 ]

2. 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 ]

3. 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 ]

4. 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$$
5. 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)

• Mast: Please take a look at how other programming-challenge questions have solved this.
• Zachary Vance: It would be helpful if you can time things yourself. How big of inputs can you handle? How much too slowly are you running? Pay especial attention to the given problem constraints.
• Zachary Vance: I'm not sure how much experience you have with programming challenges, but if you're encountering timeouts, the problem is probably one that requires a clever algorithm, not slightly better code.

Answer 1

• You wrote the lengthy box[op[1]:op[2]+1] six times. Better set i = slice(op[1], op[2] + 1) just once and then just use box[i] as in the specification.
• map with lambda is longer and slower than a list comprehension.
• Repeatedly accessing op[3] is slower than loading it from variable, and a variable lets you use the name from the specification, which is helpful.
• Using division and then math.floor is longer and slower than simply using floor division. And possibly inaccurate, too, floats have that tendency (Maybe they're safe in this case, but I'd have to think about it, and with floor division it's just a non-issue).

With all that, your function looks like this:

def operate(op, box):
 i = slice(op[1], op[2] + 1)
 if op[0] == 3:
 print(min(box[i]))
 elif op[0] == 4:
 print(sum(box[i]))
 elif op[0] == 1:
 c = op[3]
 box[i] = [x + c for x in box[i]]
 elif op[0] == 2:
 d = op[3]
 box[i] = [x // d for x in box[i]]

Alternatively you could map methods of op[3] instead of re-implementing them with lambdas:

 ...
 elif op[0] == 1:
 box[i] = map(op[3].__add__, box[i])
 elif op[0] == 2:
 box[i] = map(op[3].__rfloordiv__, box[i])

Your "main" code can also be simplified a bit, and together with the shorter code for the operations, I might just do the whole program like this:

n, q = map(int, input().split())
box = list(map(int, input().split()))
for _ in range(q):
 op, L, R, *cd = map(int, input().split())
 i = slice(L, R + 1)
 match op, *cd:
 case 1, c:
 box[i] = [b + c for b in box[i]]
 case 2, d:
 box[i] = [b // d for b in box[i]]
 case 3,:
 print(min(box[i]))
 case 4,:
 print(sum(box[i]))

Answer 2

This is a review of the C code only.

Missing includes of <math.h>, <stdio.h> and <stdlib.h> need to be corrected.

Main function ignores return value from scanf() - that's dangerous even when you think you know what input you'll receive.

main() may use null-pointer returned from malloc() - very dangerous. It's also unnecessary to cast the returned void* to assign to an object pointer.

We never free() the allocated memory. Although the runtime library should do this at program exit, it's still a good idea to do so, at least in debug builds we might want to profile with a memory checker.

int isn't necessarily large enough to represent boxi value. I suggest including <stdint.h> and using int_fast32_t for a range of ±2✕109 (initial value of 109, followed by 105 additions of 104, or the negative equivalent). We'll need a wider type than that for the sum we compute by adding up to 105 such values - probably int_fast64_t.

Use of signed int for n is questionable - especially given that we convert it to unsigned size_t when we multiply.

We probably don't need to involve floating-point or bring in the mathematics library for floor(), given we can use integer division (remember that % is usually free when evaluating /):

int floor_div(int n, int d)
{
 return n / d - (n % d < 0);
}

If we're targeting implementations old enough to require a return at the end of main(), we should make its declaration a prototype: int main(void).

In terms of program design, I'm not a fan of dispatching every request through a single operateOnBox() function with overloaded meanings on the op argument. I'd prefer something like

 while (q-->0) {
 unsigned l, r;
 int_fast32_t c, d;
 if (scanf(" 1 %u%u%" SCNdFAST32, &l, &r, &c) == 3) {
 box_add(box, l, r, c);
 } else if (scanf(" 2 %u%u%" SCNdFAST32, &l, &r, &d) == 3) {
 box_div(box, l, r, d);
 } else if (scanf(" 3 %u%u", &l, &r) == 2) {
 box_min(box, l, r);
 } else if (scanf(" 4 %u%u", &l, &r) == 2) {
 box_sum(box, l, r);
 } else {
 fputs("Unrecognised command in input.\n", stderr);
 return EXIT_FAILURE;
 }
 }

Answer 3

Python

Import

The code uses the math library. It is best to explicitly import it, although the site might import it behind the scenes:

import math

Documentation

The PEP 8 style guide recommends adding docstrings for functions. For example:

def operate(op, box):
 """
 Perform 1 of 4 defined operations.
 The op input is a list of ...
 The box input is ...
 Either print a result or modify the box input.
 """

Simpler

Since the function op[0] input will only be 1 of 4 values, you can simplify the code by replacing this elif:

elif op[0] == 2:

with:

else:

There is no need to perform that 4th check of op[0].

Layout

The code uses inconsistent indentation in the function.
The black program can be used to automatically reformat with consistent indentation.

Unused

It is strange that the variable n is set in the main code, but it is never used. You could add a comment to mention why it is not used.

Naming

Some of the variable names are not too meaningful. For example:

nq = input().split()

This would be more meaningful:

num_boxes, num_ops = input().split()

It is common to pluralize array variables. box could be boxes.

DRY

The following expression is repeated several times in the function:

op[1]:op[2]+1

Additionally, all the op array elements don't convey sufficient meaning. I realize it was convenient to pass in these values as an array, but the readability of the code really suffers. It would be better to unpack these values into variables with more meaningful names:

 op_type = op[0]
 idx1 = op[1]
 idx2 = op[2] + 1

Then the code becomes easier to read:

print(min(box[idx1 : idx2]))

op_type could even be an enumerated type (Enum).

Performance

The code looks about as compact as it can be, and I can't identify any obvious ways to make this code more efficient. That means you need to do some research to find a completely different approach or algorithm.

---

C

A lot of the coding style advice applies to the C code as well:

• Add documentation
• Give variables more meaningful names

This line:

if(op[0] == 1 || op[0] == 2)

is simpler as:

if(op[0] < 3)