Algorithm

Problem Name: Data Structures - Box Operations

Problem Link: https://www.hackerrank.com/challenges/box-operations/problem?isFullScreen=true

In this HackerRank in Data Structures - Box Operations solutions,

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 boxi . 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 <= i <= r)

  • 1 l r c: Add to each boxi . Note that c an be negative.
  • 2 l r d: Replace each boxi with [boxi/d].
  • 3 l r: Print the minimum value of any boxi.
  • 4 l r: Print the sum of all boxi.

Recall that [x] is the maximum integer y such that y <= x (e.g. [-2.5] = -3 and [-7] = -7).

Given n the value of each boxi , 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 box0 ,box1 , ..... , boxn-1 (i.e., the integers written on each box).
Each of the q subsequent lines describes an operation in one of the four formats defined above.

Constraints

  • 1 <= n,q <= 105
  • -109 <= boxi <= 109
  • 0 <= l <= r <= n - 1
  • -104 <= c <= 104
  • 2 <= d <= 109

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:

image

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  boxi where 0 <= i <= 4:
    image
  2. The second operation is 1 5 9 1, so we add c = 1 to each boxi where 5 <= i <= 9:
    image
  3. The third operation is 2 0 9 3, so we divide each boxi where 0 <= i <= 9 by d = 3 and take the floor:
    image
  4. The fourth operation is 3 0 9, so we print the minimum value of boxi for 0 <= i <= 9 , which is the result of min(-2,-1,-1,-1,0,0,0,1,1,1) = -2.
  5. The fifth operation is 4 0 9, so we print the sum of boxi for 0 <= i <= 9 , which is the result of  -2 + -1 + -1 + -1 + 0 + 0 + 0 + 1 + 1 +1 = -2.
    ... and so on.

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include<stdio.h>
#define N 110000
#define M 550000
long long tmp[M], mi[M], mx[M], sum[M];
void tpl(int v, long long c, int len)
{
    tmp[v] += c;
    sum[v] += c * len;
    mx[v] += c;
    mi[v] += c;
}
void update(int v, int l, int r)
{
    if(tmp[v])
    {
        int mid = ( l + r ) / 2;
        tpl(v+v, tmp[v], mid-l+1);
        tpl(v+v+1, tmp[v], r-mid);
        tmp[v] = 0;
    }
}
int min(int a, int b)
{
    return a < b ? a : b;
}
int max(int a, int b>
{
    return a > b ? a : b;
}
void add(int l, int r, int v, int x, int y, long long c)
{
    if( l == x && r == y )
    {
        tmp[v] += c;
        sum[v] += c * ( r - l + 1 );
        mx[v] += c;
        mi[v] += c;
        return;
    }
    else
    {
        update(v, l, r);
    }
    int mid = ( l + r ) / 2;
    if( y <= mid )
    {
        add(l, mid, v+v, x, y, c>;
    }
    else if( x > mid )
    {
        add(mid+1, r, v+v+1, x, y, c);
    }
    else
    {
        add(l, mid, v+v, x, mid, c), add(mid+1, r, v+v+1, mid+1, y, c);
    }
    sum[v] = sum[v+v] + sum[v+v+1];
    mi[v] = min(mi[v+v], mi[v+v+1]);
    mx[v] = max(mx[v+v], mx[v+v+1]);
}
const long long inf = 5e9;
int cnt;
void div(int l, int r, int v, int x, int y, long long c)
{
    cnt++;
    if( l == x && r == y && mi[v] >= mx[v]-1 && ( ( mi[v] + c * inf ) / c - inf - mi[v] ) == ( ( mx[v] + c * inf ) / c - inf - mx[v] ) )
    {
        if( mi[v] > 0 )
        {
            c = mi[v] / c - mi[v];
        }
        else
        {
            c = ( mi[v] + c * inf ) / c - inf - mi[v];
        }
        tmp[v] += c;
        sum[v] += c * ( r - l + 1 );
        mx[v] += c;
        mi[v] += c;
        return;
    }
    update(v, l, r);
    int mid = ( l + r ) / 2;
    if( y <= mid )
    {
        div(l, mid, v+v, x, y, c>;
    }
    else if( x > mid )
    {
        div(mid+1, r, v+v+1, x, y, c);
    }
    else
    {
        div(l, mid, v+v, x, mid, c), div(mid+1, r, v+v+1, mid+1, y, c);
    }
    sum[v] = sum[v+v] + sum[v+v+1];
    mi[v] = min(mi[v+v], mi[v+v+1]);
    mx[v] = max(mx[v+v], mx[v+v+1]);
}
long long minmize(int l, int r, int v, int x, int y)
{
    if( l == x && r == y )
    {
        return mi[v];
    }
    else
    {
        update(v, l, r);
    }
    int mid = ( l + r ) / 2;
    if( y <= mid )
    {
        return minmize(l, mid, v+v, x, y>;
    }
    else if( x > mid )
    {
        return minmize(mid+1, r, v+v+1, x, y);
    }
    else
    {
        return min(minmize(l, mid, v+v, x, mid), minmize(mid+1, r, v+v+1, mid+1, y));
    }
}
long long get(int l, int r, int v, int x, int y)
{
    if( l == x && r == y )
    {
        return sum[v];
    }
    else
    {
        update(v, l, r);
    }
    int mid = ( l + r ) / 2;
    if( y <= mid )
    {
        return get(l, mid, v+v, x, y>;
    }
    else if( x > mid )
    {
        return get(mid+1, r, v+v+1, x, y);
    }
    else
    {
        return get(l, mid, v+v, x, mid) + get(mid+1, r, v+v+1, mid+1, y);
    }
}
int a[N];
int main()
{
    int n, q, i;
    scanf("%d%d", &n, &q);
    for( i = 1 ; i <= n ; i++ )
    {
        scanf("%d", &a[i]), add(1, n, 1, i, i, a[i]);
    }
    for( i = 1 ; i  < = q ; i++ )
    {
        int ty, l, r;
        scanf("%d%d%d", &ty, &l, &r);
        l++;
        r++;
        if( ty == 1 )
        {
            int c;
            scanf("%d", &c);
            add(1, n, 1, l, r, c);
        }
        if( ty == 2 )
        {
            int c;
            scanf("%d", &c);
            div(1, n, 1, l, r, c);
        }
        else if( ty == 3 )
        {
            printf("%lld\n", minmize(1, n, 1, l, r));
        }
        if( ty == 4 )
        {
            printf("%lld\n", get(1, n, 1, l, r)>;
        }
        if( cnt > 1e8 )
        {
            a[-inf] = 100;
            return -1;
        }
    }
    return 0;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long LL;
inline int Div(int x , int d) {
    return x >= 0 ? x / d : -((-x + d - 1) / d);
}

int n , m , a[N];

inline int id(int l , int r) {
    return l + r | l != r;
}
#define MID int mid = l + r >> 1
#define Left l , mid
#define Right mid + 1 , r

struct stree {
    int mx , mn , f;
    LL s;
    void add(int w , int len) {
        mx += w;
        mn += w;
        f += w;
        s += (LL)len * w;
    }
} t[N << 1];

void pushdown(int p , int l , int mid , int r) {
    if (t[p].f) {
        t[id(Left)].add(t[p].f , mid - l + 1);
        t[id(Right)].add(t[p].f , r - mid);
        t[p].f = 0;
    }
}
void pushup(int p , int l , int mid , int r) {
    int L = id(Left) , R = id(Right);
    t[p].mx = max(t[L].mx , t[R].mx);
    t[p].mn = min(t[L].mn , t[R].mn);
    t[p].s = t[L].s + t[R].s;
}
void build(int l , int r) {
    int p = id(l , r);
    t[p].f = 0;
    if (l == r) {
        t[p].mx = t[p].mn = t[p].s = a[l];
    } else {
        MID;
        build(Left);
        build(Right);
        pushup(p , l , mid , r);
    }
}
void add(int l , int r , int top , int bot , int w) {
    int p = id(l , r);
    if (top  < = l && r <= bot) {
        t[p].add(w , r - l + 1);
    } else {
        MID; pushdown(p , l , mid , r);
        if (top  < = mid) add(Left , top , bot , w);
        if (bot > mid) add(Right , top , bot , w);
        pushup(p , l , mid , r);
    }
}
LL sum(int l , int r , int top , int bot) {
    int p = id(l , r);
    if (top  < = l && r <= bot) {
        return t[p].s;
    } else {
        MID; pushdown(p , l , mid , r); LL res = 0;
        if (top  < = mid) res += sum(Left , top , bot);
        if (bot > mid) res += sum(Right , top , bot);
        return res;
    }
}
int minimum(int l , int r , int top , int bot) {
    int p = id(l , r);
    if (top  < = l && r <= bot) {
        return t[p].mn;
    } else {
        MID; pushdown(p , l , mid , r); int res = 0x7FFFFFFF;
        if (top  < = mid) res = min(res , minimum(Left , top , bot));
        if (bot > mid) res = min(res , minimum(Right , top , bot));
        return res;
    }
}
void divide(int l , int r , int top , int bot , int d) {
    int p = id(l , r);

    bool stop = 0;
    if (top  < = l && r <= bot) {
        if (t[p].mx == t[p].mn) stop = 1;
        int delta = t[p].mx - t[p].mn;
        int t1 = Div(t[p].mx , d);
        int t0 = Div(t[p].mn , d);
        if (t1 - t0 == delta) stop = 1;
    }

    if (stop || l == r) {
        t[p].add(Div(t[p].mx , d) - t[p].mx , r - l + 1);
    } else {
        MID; pushdown(p , l , mid , r);
        if (top  < = mid) divide(Left , top , bot , d);
        if (bot > mid) divide(Right , top , bot , d);
        pushup(p , l , mid , r);
    }

}


int main() {
    scanf("%d%d" , &n , &m);
    for (int i = 0 ; i  <  n ; ++ i) {
        scanf("%d" , a + i);
    }
    build(0 , n - 1);
    for (int i = 0 ; i  <  m ; ++ i) {
        int o , l , r , w;
        scanf("%d%d%d" , &o , &l , &r);
        if (o == 1) {
            scanf("%d" , &w);
            add(0 , n - 1 , l , r , w);
        }
        if (o == 2) {
            scanf("%d" , &w);
            divide(0 , n - 1 , l , r , w);
        }
        if (o == 3) {
            printf("%d\n" , minimum(0 , n - 1 , l , r));
        }
        if (o == 4) {
            printf("%lld\n" , sum(0 , n - 1 , l , r));
        }
    }
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - Java Programming


import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Solution {

  static int func(int p, int q) {
    if (p >= 0) {
      return p / q;
    }
    return -((-p + q - 1) / q);
  }

  static final int inf = (int) (2e9) + (int) (1e8);

  static class Tree {
    long[] sum;
    int[] vmin;
    int[] vmax;
    int[] add;
    int base;
    
    Tree(int n) {
        base = (1 << (32 - Integer.numberOfLeadingZeros(n)));
      sum = new long[base * 2];
      vmin = new int[base * 2];
      vmax = new int[base * 2];
      add = new int[base * 2];
    }

    private void update(int u) {
      vmin[u] = Math.min(vmin[u * 2], vmin[u * 2 + 1]);
      vmax[u] = Math.max(vmax[u * 2], vmax[u * 2 + 1]);
      sum[u] = sum[u * 2] + sum[u * 2 + 1];
    }

    private void putVal(int u, int val, int len) {
      add[u] += val;
      vmin[u] += val;
      vmax[u] += val;
      sum[u] += val * len;
    }

    private void push(int u, int cl, int cr) {
      if (add[u] != 0) {
        int len = (cr - cl) / 2;
        putVal(u * 2, add[u], len);
        putVal(u * 2 + 1, add[u], len);
        add[u] = 0;
      }
    }

    long getSum(int l, int r) {
        return getSum(l, r, 1, 0, base);
    }
    
    private long getSum(int l, int r, int v, int cl, int cr) {
      if (l  < = cl && cr <= r) {
        return sum[v];
      }
      if (r <= cl || cr <= l) {
        return 0;
      }
      int cc = (cl + cr) / 2;
      push(v, cl, cr);
      return getSum(l, r, v * 2, cl, cc) + getSum(l, r, v * 2 + 1, cc, cr);
    }

    int getMin(int l, int r) {
        return getMin(l, r, 1, 0, base);
    }
    
    private int getMin(int l, int r, int v, int cl, int cr) {
      if (l  < = cl && cr <= r) {
        return vmin[v];
      }
      if (r <= cl || cr <= l) {
        return inf;
      }
      int cc = (cl + cr) / 2;
      push(v, cl, cr);
      return Math.min(getMin(l, r, v * 2, cl, cc), getMin(l, r, v * 2 + 1, cc, cr));
    }

    void put(int l, int r, int delta) {
        put(l, r, delta, 1, 0, base);
    }
    
    private void put(int l, int r, int delta, int v, int cl, int cr) {
      if (l  < = cl && cr <= r) {
          putVal(v, delta, cr - cl);
        return;
      }
      if (r  < = cl || cr <= l) {
        return;
      }
      int cc = (cl + cr) / 2;
      push(v, cl, cr);
      put(l, r, delta, v * 2, cl, cc);
      put(l, r, delta, v * 2 + 1, cc, cr);
      update(v);
    }

    private void divide(int l, int r, int x) {
        divide(l, r, x, 1, 0, base);
    }
    
    private void divide(int l, int r, int x, int v, int cl, int cr) {
      if (x == 1) {
        return;
      }
      if (l  < = cl && cr <= r) {
        int d1 = func(vmin[v], x) - vmin[v];
        int d2 = func(vmax[v], x) - vmax[v];
        if (d1 == d2) {
            putVal(v, d1, cr - cl);
          return;
        }
      }
      if (r  < = cl || cr <= l) {
        return;
      }
      int cc = (cl + cr) / 2;
      push(v, cl, cr);
      divide(l, r, x, v * 2, cl, cc);
      divide(l, r, x, v * 2 + 1, cc, cr);
      update(v);
    }

    void build(int n) {
      for (int i = n + base; i  <  2 * base; i++) {
        vmin[i] = inf;
        vmax[i] = -inf;
      }
      for (int i = base - 1; i > 0; i--) {
        update(i);
      }
    }
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int q = Integer.parseInt(st.nextToken());

    Tree t = new Tree(n);

    int[] box = new int[n];
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i  <  n; i++) {
      int item = Integer.parseInt(st.nextToken());
      box[i] = item;
      t.sum[i + t.base] = t.vmin[i + t.base] = t.vmax[i + t.base] = item;
    }
    t.build(n);

    for (int i = 0; i  <  q; i++) {
      st = new StringTokenizer(br.readLine());
      int op = Integer.parseInt(st.nextToken());
      int l = Integer.parseInt(st.nextToken());
      int r = Integer.parseInt(st.nextToken()) + 1;
      if (op == 1) {
        int x = Integer.parseInt(st.nextToken());
        t.put(l, r, x);
      } else if (op == 2) {
        int x = Integer.parseInt(st.nextToken());
        t.divide(l, r, x);
      } else if (op == 3) {
        bw.write(t.getMin(l, r) + "\n");
      } else if (op == 4) {
        bw.write(t.getSum(l, r) + "\n");
      }
    }

    bw.close();
    br.close();
  }
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration

Previous
[Solved] Find the permutation solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Max Transform solution in Hackerrank - Hacerrank solution C, C++, java,js, Python