[Solved] Arithmetic Progressions solution in Hackerrank - Hacerrank solution C, C++, java,js, Python

Algorithm

Problem Name: Data Structures - Arithmetic Progressions

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

In this HackerRank in Data Structures - Arithmetic Progressions solutions,

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.

Code Examples

#1 Code Example with C Programming

Code - 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;
}

Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - 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;
}

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.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();
  }
}

Copy The Code & Try With Live Editor

#4 Code Example with Python Programming

Code - Python Programming


import sys

M = 1000003
F = [1] * M
for i in range(1, M): 
    F[i] = (i * F[i-1]) % M
    
def f(i): 
    return F[i] if i < M else 0

def build(a, i, j):
    if i + 1 == j:
        return (i, j, None, None, a[i][1], a[i][1], a[i][0], pow(a[i][0], a[i][1], M))
    l = build(a, i, (i + j) // 2)
    r = build(a, (i + j) // 2, j)
    K = l[5] + r[5]
    d = (l[6] * r[6]) % M
    V = (l[7] * r[7]) % M
    return (i, j, l, r, 0, K, d, V)

def update(t,i,j,p):
    ti, tj, tl, tr, tp, tK, td, tV = t
    if tj <= i or j <= ti: return t, 0, 1
    if i <= ti and tj <= j:
        tp += p
        dk = (tj - ti) * p
        dv = pow(td, p, M) if dk < M else 0
    else:
        tl, lk, lv = update(tl, i, j, p) if tl != None else (tl, 0, 1)
        tr, rk, rv = update(tr, i, j, p) if tr != None else (tr, 0, 1)
        dk, dv = lk + rk, (lv * rv) % M
    tK += dk
    tV = (tV * dv) % M
    return (ti, tj, tl, tr, tp, tK, td, tV), dk, dv

def queryK(t, i, j, p = 0):
    ti, tj, tl, tr, tp, tK, td, tV = t
    if tj < i or j < ti: return 0
    if i <= ti and tj <= j: return tK + (tj - ti) * p
    lk = queryK(tl, i, j, p + tp) if tl != None else 0
    rk = queryK(tr, i, j, p + tp) if tr != None else 0
    return lk + rk

def queryV(t, i, j, p = 0):
    ti, tj, tl, tr, tp, tK, td, tV = t
    if tj < i or j < ti: return 1
    if i <= ti and tj <= j: return (tV * pow(td, p, M)) % M
    lv = queryV(tl, i, j, p + tp) if tl != None else 1
    rv = queryV(tr, i, j, p + tp) if tr != None else 1
    return (lv * rv) % M

n = int(sys.stdin.readline())
a = [list(map(int,sys.stdin.readline().split()[1:])) for i in range(n)]
T = build(a, 0, len(a))
for q in range(int(sys.stdin.readline())):
    x = list(map(int,sys.stdin.readline().split()))
    if x[0]:
        T = update(T, x[1] - 1, x[2], x[3])[0]
    else:
        k = queryK(T, x[1] - 1, x[2])
        v = queryV(T, x[1] - 1, x[2]) if k < M else 0
        print('%d %d'%(k, (v * f(k)) % M))

Copy The Code & Try With Live Editor

Demonstration

Previous
[Solved] Swaps and Sum solution in Hackerrank - Hacerrank solution C, C++, java,js, Python

Next
[Solved] Coolguy and Two Subsequences solution in Hackerrank - Hacerrank solution C, C++, java,js, Python

Try With Live Editor

Category - Hacker Rank Online Judge Maniruzzaman Akash 1 year ago 328 0