HackerRank Arithmetic Progressions problem solution

In this HackerRank Arithmetic Progressions problem solution, you are given an arithmetic progression with the first term and common difference. we need to find the smallest k for which the kth difference of the sequence is a constant. we also need to find the value of constant.

Problem solution in 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.StringTokenizer;

public class Solution {

  static final int MOD = 1_000_003;
  static long[] d;
  static long[] p;
  static long[] dp;
  static long[] dlt;

  static long power(long a, long n) {
    long r = 1;
    for (; n > 0; n >>= 1, a = (a*a) % MOD) {
      if ((n & 1) > 0) {
        r = (r*a) % MOD;
      }
    }
    return r;
  }

  static void apply(int n, int i, long v) {
    dlt[i] += v;
    p[i] += v << Integer.numberOfLeadingZeros(i) - Integer.numberOfLeadingZeros(n);
    dp[i] = (dp[i]*power(d[i], v))%MOD;
  }

  static void mconcat(int i) {
    p[i] = p[2*i]+p[2*i+1];
    dp[i] = (dp[2*i]*dp[2*i+1])%MOD;
  }

  static void untag(int n, int i) {
    if (i < 0 || n <= i) return;
    i += n;
    for (int j, h = 31 - Integer.numberOfLeadingZeros(n); h>0; h--)
      if ((dlt[j = i >> h]) > 0) {
        apply(n, 2*j, dlt[j]);
        apply(n, 2*j+1, dlt[j]);
        dlt[j] = 0;
      }
  }

  static void add(int n, int l, int r, long v) {
    boolean lf = false;
    boolean rf = false;
    untag(n, l-1);
    untag(n, r);
    for (l += n, r += n; l < r; ) {
      if ((l & 1) > 0) {
        lf = true;
        apply(n, l++, v);
      }
      l >>= 1;
      if (lf) {
        mconcat(l-1);
      }
      if ((r & 1) > 0) {
        rf = true;
        apply(n, --r, v);
      }
      r >>= 1;
      if (rf) {
        mconcat(r);
      }
    }
    for (l--; (l >>= 1) > 0 && (r >>= 1) > 0; ) {
      if (lf || l == r) {
        mconcat(l);
      }
      if (rf && l != r) {
        mconcat(r);
      }
    }
  }
  
  static long[] query(int n, int l, int r) {
    long ps = 0;
    long dps = 1;
    untag(n, l-1);
    untag(n, r);
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if ((l & 1) > 0) {
        ps += p[l];
        dps = dps*dp[l]%MOD;
        l++;
      }
      if ((r & 1) > 0) {
        r--;
        ps += p[r];
        dps = dps*dp[r]%MOD;
      }
    }
    return new long[] {ps, dps};
  }
  
  static int[] factorial(final int n) {
    final int[] vFactorial = new int[n];
    vFactorial[0] = 1;
    for (int i = 1; i < n; i++) {
        vFactorial[i] = (int)(((long)vFactorial[i - 1] * i) % MOD);
    }
    return vFactorial;
  }

  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")));

    int[] fact = factorial(MOD);
    
    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int nn = 1;
    while (nn < n) nn *= 2;
    
    d = new long[2 * nn];
    p = new long[2 * nn];
    dp = new long[2 * nn];
    dlt = new long[2 * nn];
    
    for (int i = 0; i < n; i++) {
      st = new StringTokenizer(br.readLine());
      st.nextToken();
      d[nn+i] = Integer.parseInt(st.nextToken());
      p[nn+i] = Integer.parseInt(st.nextToken());
      dp[nn+i] = power(d[nn+i], p[nn+i]);
    }
    for (int i = nn; --i >= 1; ) {
      d[i] = (d[2*i]*d[2*i+1])%MOD;
      mconcat(i);
    }
    
    st = new StringTokenizer(br.readLine());
    int q = Integer.parseInt(st.nextToken());
    for (int i = 0; i < q; i++) {
      st = new StringTokenizer(br.readLine());
      int op = Integer.parseInt(st.nextToken());
      int l = Integer.parseInt(st.nextToken()) - 1;
      int r = Integer.parseInt(st.nextToken());
      if (op > 0) {
        int num = Integer.parseInt(st.nextToken());
        add(nn, l, r, num);
      }
      else {
        long[] ans = query(nn, l, r);
        int ps = (int) ans[0];
        long dps = (ans[1]+MOD)%MOD;
        bw.write(ps + " " + (ps >= MOD ? 0 : fact[ps]*dps%MOD) + "\n");
      }
    }
    
    bw.newLine();
    bw.close();
    br.close();
  }
}

Problem solution in C++ programming.

#include <cstdio>
#include <iostream>
using std::swap;
using std::cout;
using std::endl;

typedef long long LL;
const LL Mod=1000003;
const int N=100001;
const LL INF=1LL<<62;

LL f[Mod+10];


LL power(LL base, LL k)
{
    LL res=1;
    while(k){
        if(k&1) res=(res*base)%Mod;
        base=(base*base)%Mod;
        k>>=1;
    }  
    return res;
}

struct Node{
    int l,r;//sum;
    LL K;
    LL sk;
    LL V;
    LL V2;
    LL s;
    Node *lc,*rc;
    LL getK()
    {
        return K+sk*(r-l+1LL);    
    }
    
    LL getV2()
    {
        return (power(V,s)*V2)%Mod;
        //return power(V,s);
    }
};

Node buf[200010];
Node* root;
int pt=0;


Node*  New()
{
    buf[pt].lc=buf[pt].rc=NULL;
    buf[pt].l =buf[pt].r =-INF;
    buf[pt].K=-1;
    buf[pt].V=-1;
    buf[pt].s=-1;
    return buf+pt++;
}

void build(Node* root, int l,int r)
{
    root->l=l;
    root->r=r;
    root->K=0;
    root->V=1;
    root->V2=1;
    root->s=0;
    root->sk=0;

    if(l==r)return;

    root->lc=New();
    root->rc=New();

    int mid=(l+r)/2;
    build(root->lc,l,mid);
    build(root->rc,mid+1,r);
}

void fresh(Node* root)
{
    root->K = root->lc->getK() + root->rc->getK();
    root->V = (root->lc->V*root->rc->V )%Mod;
    root->V2 = (root->lc->getV2()*root->rc->getV2())%Mod;
}

LL queryK(Node* root,int l, int r)
{
    if(root->l==l && root->r==r){
        return root->getK();
    }    
    int mid = (root->l+root->r)/2;
    if(l>mid){
        LL res=queryK(root->rc,l,r);
        return res+root->sk*(r-l+1LL);
    }
    else if(r<=mid){
        LL res=queryK(root->lc,l,r);
        return res+root->sk*(r-l+1LL);
    }
    else{
        LL a = queryK(root->lc,l,mid);
        LL b = queryK(root->rc,mid+1,r);
        return a+b+root->sk*(r-l+1LL);        
    }
    return -INF;
}

LL queryV(Node* root,int l, int r, int ac)
{
    //printf("root->l=%d root->r=%d root->s=%I64d root->v=%I64d root->k=%I64d\n",
    //root->l,root->r,root->s,root->V,root->K);
    
    if(root->l==l && root->r==r){
        //return power(root->V,ac+root->s);
        LL res = root->getV2();
        return (res*power(root->V,ac))%Mod;
    }    
    int mid = (root->l+root->r)/2;
    if(l>mid){
        //LL res=queryV(root->rc,l,r);
        //return power(res,root->s+1);
        //return (res*root->getV())%Mod;
        
        return queryV(root->rc,l,r,ac+root->s);
    }
    else if(r<=mid){
        //LL res=queryV(root->lc,l,r);
        //return power(res,root->s+1);
        //return (res*root->getV())%Mod;
        
        return queryV(root->lc,l,r,ac+root->s);
    }
    else{
        LL a = queryV(root->lc,l,mid,ac+root->s);
        LL b = queryV(root->rc,mid+1,r,ac+root->s);
        LL res = (a*b)%Mod;
        //return power((a*b)%Mod,root->s+1);        
        //return (res*root->getV())%Mod;
        
        return res;
    }
    return -INF;
}


void add( Node* root, int l, int r, int delta)
{
    //printf("root->l=%d root->r=%d l=%d r=%d val=%d\n",root->l,root->r,l,r,val);
    
    if(root->l==l && root->r==r){
        root->s += delta;
        root->sk += delta;
        return;
    }

    int mid = (root->l+root->r)/2;
    if(l>mid){
        add(root->rc,l,r,delta);
    }
    else if(r<=mid){
        add(root->lc,l,r,delta);
    }
    else{
        add(root->lc,l,mid,delta);
        add(root->rc,mid+1,r,delta);
    }
    fresh(root);
}

void update(Node* root,int l,int r,int d,int k)
{
    //printf("update, l=%d r=%d val=%d\n",root->l,root->r,val);
    if(l!=r){
        puts("currently only update single element");
    }

    if(root->l==l && root->r==r){
        //printf("index=%d is updated, val=%d\n",l,val);
        root->V=d;
        root->K=k;
        root->s=k;
        root->sk=0;
        return;
    }

    int mid = (root->l+root->r)/2;

    if(l>mid){
        //puts("should not execute");
        update(root->rc,l,r,d,k);
    }
    else if(r<=mid){
        update(root->lc,l,r,d,k);
    }
    else{
        //puts("should not execute");
        //add(root->lc,l,mid,val);
        update(root->rc,mid+1,r,d,k);
    }
    
    fresh(root);
}


void output(Node* p, int l, int r)
{
    if(p->l==l && p->r==r){
        if(l==r){
            printf("index=%d K=%I64d V=%I64d\n",l,queryK(root,l,l),queryV(root,l,l,0));
        }
        else{
            output(p->lc,l,(l+r)/2);
            output(p->rc, (l+r)/2+1, r);    
        }
        return;
    }    
    int mid=(p->l+p->r)/2;
    if(l>mid){
        output(p->rc,l,r);    
    }
    else if(r<=mid){
        output(p->lc,l,r);        
    }
    else{
        output(p->lc,l,mid);
        output(p->rc,mid+1,r);    
    }
}

void Init()
{
    root=New();
    build(root,1,N);
    f[0]=1;
    for(int i=1;i<Mod;++i)
        f[i]=(i*f[i-1])%Mod;
}

int main()
{
    Init();
    /*
    output(root,1,10);
    update(root,2,2,0);
    add(root,3,N,2);
    puts("add(root,3,N,2)");
    output(root,1,10);
    
    update(root,1,1,0);
    add(root,2,N,1);
    
    puts("add(root,2,N,1)");
    output(root,1,10);
    */
    //return 0;
    char cmd[10];

    int n,q;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int a,d,p;
        scanf("%d%d%d",&a,&d,&p);
        update(root,i,i,d,p);        
    }
    
    scanf("%d",&q);
    while(q--){
        int c,a,b,delta;
        scanf("%d",&c);
        
        if(!c){
            scanf("%d%d",&a,&b);      
            LL r1 = queryK(root,a,b);
            LL r2 = queryV(root,a,b,0);
            //printf("K=%I64d V=%I64d\n",r1,r2);
            r2 = r1<Mod ? (f[r1]*r2)%Mod : 0;
            
            cout<<r1<<" "<<r2<<endl;    
        }
        else{
            scanf("%d%d%d",&a,&b,&delta);  
            add(root,a,b,delta);
        }  

        //output(root,1,10);
    }


    return 0;
}

Problem solution in C programming.

#include "stdio.h"

#define T (1<<17)
#define MOD 1000003

int n, q, cmd, a, b, v, d[T], p[T];
long long fac[MOD], base[2*T], power[2*T], prod[2*T], stale[2*T], ans_pow, ans_prod;

long long mult( long long a, long long b )
{
    return ( a * b ) % MOD;
}

long long mod_pow( long long b, long long x )
{
    if( x == 0 ) return 1;
    return mult( x % 2 ? b : 1, mod_pow( mult( b, b ), x / 2 ) );
}

void init( int x, int i, int j )
{
    if( i + 1 == j )
    {
        base[x] = d[i], power[x] = p[i], prod[x] = mod_pow( d[i], p[i] );
        return;
    }

    int y = 2*x, z = 2*x+1, k = (i+j+1)/2;
    init( y, i, k ), init( z, k, j );
    base[x] = mult( base[y], base[z] );
    power[x] = power[y] + power[z];
    prod[x] = mult( prod[y], prod[z] );
}

void push_update( int x, int p, int sz )
{
    prod[x] = mult( prod[x], mod_pow( base[x], p ) );
    power[x] += p * sz;
    stale[x] += p;
}

void query( int x, int i, int j )
{
    if( a >= j || i >= b ) return;
    if( a <= i && j <= b )
    {
        if( cmd ) push_update( x, v, j - i );
        else ans_pow += power[x], ans_prod = mult( ans_prod, prod[x] );
        return;
    }

    int y = 2*x, z = 2*x+1, k = (i+j+1)/2;
    if( stale[x] )
    {
        push_update( y, stale[x], k - i );
        push_update( z, stale[x], j - k );
        stale[x] = 0;
    }
    query( y, i, k ), query( z, k, j );

    power[x] = power[y] + power[z];
    prod[x] = mult( prod[y], prod[z] );
}

int main()
{
    int i;

    fac[0] = 1;
    for( i = 1; i < MOD; i++ ) fac[i] = mult( i, fac[i-1] );

    scanf( "%d", &n );
    for( i = 0; i < n; i++ ) scanf( "%d%d%d", &q, &d[i], &p[i] );
    init( 1, 0, n );

    scanf( "%d", &q );
    while( q-- )
    {
        scanf( "%d%d%d", &cmd, &a, &b );
        a--;
        if( cmd ) scanf( "%d", &v );
        else ans_pow = 0, ans_prod = 1;
        query( 1, 0, n );
        if( !cmd )
        {
            ans_prod = ans_pow < MOD ? mult( ans_prod, fac[ans_pow] ) : 0;
            printf( "%lld %lld\n", ans_pow, ans_prod );
        }
    }

    return 0;
}