In this HackerRank Jaggu Playing with Balloons problem solution you are given q number of queries which can be either an Update Query or Report Query.Each Update Query is followed by at least 1 report query. for each query we need to output the answer in a separate line.

HackerRank Jaggu Playing with Balloons problem solution


Problem solution in Java Programming.

import java.util.*;
import java.io.*;

public class JagguWaterBall {
    static long[] buckets = null;

    static void go() {
        int q = in.nextInt();

        buckets = new long[1000002];
        while (q-- > 0) {
            String command = in.nextString();
            if (command.charAt(0) == 'U') {
                int p = in.nextInt();
                int m = in.nextInt();
                int plus = in.nextInt();
                update(p, m, plus);
            } else {
                int p1 = in.nextInt();
                int p2 = in.nextInt();
                //out.println(read(p2) - read(p1-1));
                out.println(getBetween(p1-1, p2));
            }
        }
    }

    static void update(int pos, int m, int plus) {
        int N = 1000000;  //1 million
        for (int i = 1; i <= 50; i++) {
            //System.out.println("i= " + i);
            int back = pos;
            //System.out.println("start pos = " + pos);
            for (int j = 1; j <= 1000; j++) {
                //System.out.println("pos1 = " + pos);
                //buckets[pos] += m;
                add(pos, m);
                int s, in = getBITs(pos);
                for (int k = 0; ; k++) {
                    //System.out.println("k = " + k);
                    s = pos + (1<<k);
                    if (getBITs(s) <= in) {
                        in = getBITs(s);
                        pos = s;
                        if (pos > N) {
                            //System.out.println("pos = " + pos);
                            break;
                        }
                        //System.out.println("pos2 = " + pos);
                        //buckets[pos] += m;
                        add(pos, m);
                    }
                }
                //System.out.println(" j = " + j + ": " + pos);
                pos = pos - N;
                if (pos == 48576 && j < 1000) {
                    long val = (1000 - j) * m;
                    add(48576, val);
                    add(48640, val);
                    add(49152, val);
                    add(65536, val);
                    add(131072, val);
                    add(262144, val);
                    add(524288, val);
                    break;
                }
            }
            pos = back + plus;
            //System.out.println("pos3 = " + pos);
            if (pos > N)
                pos -= N;
        }
    }

    static long getBetween(int p1, int p2) {
        long ret = 0;
        while(p1 != p2) {
            if (p2 > p1) {
                ret += buckets[p2];
                p2 -= (p2 & -p2);
            } else {
                ret -= buckets[p1];
                p1 -= (p1 & -p1);
            }
        }
        return ret;
    }

    static long read(int idx) {
        long sum = 0;
        while(idx > 0) {
            sum += buckets[idx];
            idx -= (idx & -idx);
        }
        return sum;
    }

    static void add(int idx, long x) {
        while(idx <= 1000000) {
            buckets[idx] += x;
            idx += (idx & -idx);
        }
    }

    static int getBITs(long x) {
        int ret = 0;
        while (x > 0) {
            ret++;
            x &= x - 1;
        }
        return ret;
    }

    static InputReader in;
    static PrintWriter out;

    public static void main(String[] args) {
        in = new InputReader(System.in);
        out = new PrintWriter(System.out);

        go();

        out.close();
    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int nextInt() {
            return (int) nextLong();
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String nextString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder sb = new StringBuilder(1024);
            do {
                sb.append((char) c);
                c = read();
            } while (!isSpaceChar(c));
            return sb.toString();
        }

        public static boolean isSpaceChar(int c) {
            switch (c) {
                case -1:
                case ' ':
                case '\n':
                case '\r':
                case '\t':
                    return true;
                default:
                    return false;
            }
        }
    }
}


Problem solution in C++ programming.

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<assert.h>
using namespace std;
#define MaxN 1000000
#define rep1 50
#define rep2 1000
#define MaxVal MaxN
typedef long long int ll;
int special[]={1,983041,999425,999937,1000001};
int bouncedat[]={48576,15808,448,64};
ll tree[MaxN+1];
ll read(int pos)
{
    ll sum=0;
    while(pos){
        sum = sum + tree[pos];
        pos-=(pos&(-pos));
    }
    return sum;
}
void update(int pos,ll v)
{
    ll b=v;
    while(pos<=MaxVal){
        tree[pos]+=v;
        v+=b;
        pos+=(pos&(-pos));
    }
}
int main()
{
    int N=MaxN,Q,x,y,plus,j,counter[4],where;
    char ch;
    scanf("%d",&Q);
    for(int i=0;i<Q;i++){
        scanf(" %c%d%d",&ch,&x,&y);
        if(ch=='U'){
            where=0;
            scanf("%d",&plus);
            memset(counter,0,sizeof(counter));
            for(j=1;j<=rep1;j++){
                update(x,y);
                if(x>=special[where] && x<special[where+1]) counter[where]++;
                else{
                    while(1){
                        where++;
                        if(where==4)    where=0;
                        if(x>=special[where] && x<special[where+1]){
                            counter[where]++;
                            break;
                        }
                    }
                }
                x=x+plus;
                if(x>N) x=x-N;
            }
            for(j=0;j<4;j++){
                if(counter[j]!=0)
                update(bouncedat[j],y*(counter[j]));
            }
            update(bouncedat[0],(ll)y*(ll)(rep2-2)*(ll)rep1);
        }
        else    printf("%lld\n",read(y)-read(x-1));
    }
    return 0;
}


Problem solution in C programming.

#include<stdio.h>

int arr[]={1,983041,999425,999937,1000001};
int ar1[]={48576,15808,448,64};
long long int ar2[1000001];

long long int ans(int a)
{
    long long int sum=0;
    while(a)
    {
        sum = sum + ar2[a];
        a-=(a&(-a));
    }
    return sum;
}

void query(int a,long long int b)
{
    long long int c=b;
    while(a<=1000000)
    {
        ar2[a]+=b;
        b+=c;
        a+=(a&(-a));
    }
}

int main()
{
    int i,N=1000000,Q,pos1,pos2,plus,j,temp;
    char qry;
    scanf("%d",&Q);

    for(i=0;i<Q;i++){
        scanf(" %c",&qry);
        scanf("%d %d",&pos1,&pos2);
        if(qry =='U'){
            temp=0;
            int counter[4]={0};
            scanf("%d",&plus);
    
            for(j=1;j<=50;j++)
            {
                query(pos1,pos2);
                if(pos1>=arr[temp] && pos1<arr[temp+1]) 
                    counter[temp]++;
                else
                {
                    while(1)
                    {
                        temp++;
                        if(temp==4)    
                            temp=0;
                        if(pos1>=arr[temp] && pos1<arr[temp+1])
                        {
                            counter[temp]++;
                            break;
                        }
                    }
                }
                pos1=pos1+plus;
                if(pos1>N) 
                    pos1=pos1-N;
            }

            for(j=0;j<4;j++){
                if(counter[j]!=0)
                    query(ar1[j],pos2*(counter[j]));
            }

            query(ar1[0],(long long int)pos2*49900);
        }
        else    
            printf("%lld\n",ans(pos2)-ans(pos1-1));
    }
    return 0;
}