HackerRank Polynomial Division problem solution

In this HackerRank Polynomial Division problem, we have given the values of n, a,b and q queries, perform each query in order.

Problem solution in Python programming.

#!/bin/python3

import math
import os
import random
import re
import sys

# returns d, x, y so that gcd(a, b) = d and ax + by = d
def extended_euclidean_alg(a,b):
    # starts out as p[0] = P_{-1}, p[1] = P_0 and same for q
    # in general it's the previous 2 terms, P_{i-1}, P_{i-2}
    p = [0, 1]
    q = [1, 0]
    counter = 1
    while b != 0:
        quo = a//b
        rem = a % b
        newP = quo*p[1] + p[0]
        newQ = quo*q[1] + q[0]
        p[0] = p[1]
        p[1] = newP
        q[0] = q[1]
        q[1] = newQ
        a = b
        b = rem
        counter = (counter + 1) % 2
    minusOne = (counter-1) % 2
    return a, q[0]*((-1)**minusOne), p[0]*((-1)**(counter))

def leastSigBit(num):
    return (num & -num)

# implementation of a Fenwick tree
class PrefixSumTree(object):
    def __init__(self,array):
        l = len(array)
        self.sums = [0] * l
        for i in range(1,l):
            cl = i - leastSigBit(i)
            for j in range(cl+1,i+1):
                self.sums[i] = (self.sums[i] + array[j]) % p

    def sum(self,i):
        sum = 0
        while i > 0:
            sum = (sum + self.sums[i]) % p
            i -= leastSigBit(i)
        return sum

    # adds toAdd to the ith element of array
    def add(self,i,toAdd):
        while i <= len(self.sums)-1:
            self.sums[i] = (self.sums[i] + toAdd) % p
            i += leastSigBit(i)

p = 10**9 + 7

def polynomialDivision(a, b, c, queries):
    res = []
    a_inv = extended_euclidean_alg(p, a)[2]
    x = -b*a_inv % p
    # if x != 0 then we have to build the sum tree
    if x != 0:
        l = len(c)
        # polyArray[i+1] = c[i]*x^i % p and polyArray[0] = 0
        polyArray = [0] * (l+1)
        polyArray[1] = c[0]
        # powsOfX[i] = x^i % p
        powsOfX = [1] * l
        for i in range(1,l):
            newPow = (powsOfX[i-1]*x) % p
            powsOfX[i] = newPow
            polyArray[i+1] = (c[i]*newPow) % p
        sumTree = PrefixSumTree(polyArray)
    for q in queries:
        if q[0] == 1:
            # compute how much we need to add for the sum
            toAdd = q[2]-c[q[1]]
            # update the array c with our new entry q[2]
            c[q[1]] = q[2]
            if x != 0:
                # then we add the appropriate amount to our prefix sums.
                # since sumTree keeps track of sum c_i * x^i we multiply by the 
                # appropriate power of x
                sumTree.add(q[1]+1,(toAdd*(powsOfX[q[1]])) % p)
        else:
            # remember c is zero indexed but sumTree is one indexed
            # so we do sum(q[2]+1) - sum(q[1]) instead of sum(q[2]) - sum(q[1]-1)
            pOfX = c[q[1]] if x == 0 else (sumTree.sum(q[2]+1) - sumTree.sum(q[1])) % p
            if pOfX == 0:
                res.append("Yes")
            else:
                res.append("No")
    return res


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nabq = input().split()

    n = int(nabq[0])

    a = int(nabq[1])

    b = int(nabq[2])

    q = int(nabq[3])

    c = [int(t) for t in input().rstrip().split()]

    queries = []

    for _ in range(q):
        queries.append([int(t) for t in input().rstrip().split()])

    result = polynomialDivision(a, b, c, queries)

    fptr.write('n'.join(result))
    fptr.write('n')

    fptr.close()

Problem solution in Java Programming.

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

public class Solution {

    static final int MOD = 1_000_000_007;
    
    static class SegmentTree {
      int st[];
      int n;

      public SegmentTree(int n) {
          this.n = n;
        int x = (int) (Math.ceil(Math.log(n) / Math.log(2)));

        int maxSize = 2 * (int) Math.pow(2, x) - 1;
        st = new int[maxSize];
      }

      int getMid(int s, int e) {
        return s + (e - s) / 2;
      }

      long getSum(int ss, int se, int qs, int qe, int si) {
        if (qs <= ss && qe >= se) {
          return st[si];
        }

        if (se < qs || ss > qe) {
          return 0;
        }

        int mid = getMid(ss, se);
        return sum(getSum(ss, mid, qs, qe, 2 * si + 1), 
            getSum(mid + 1, se, qs, qe, 2 * si + 2));
      }

      void updateValue(int ss, int se, int i, int diff, int si) {
        if (i < ss || i > se) {
          return;
        }

        st[si] = (int) sum(st[si], diff);
        if (se != ss) {
          int mid = getMid(ss, se);
          updateValue(ss, mid, i, diff, 2 * si + 1);
          updateValue(mid + 1, se, i, diff, 2 * si + 2);
        }
      }

      void updateValue(int arr[], int i, int newVal) {
        int diff = newVal - arr[i];

        arr[i] = newVal;

        updateValue(0, n - 1, i, diff, 0);
      }

      long getSum(int qs, int qe) {
        return getSum(0, n - 1, qs, qe, 0);
      }

      void construct(int arr[]) {
        construct(arr, 0, arr.length - 1, 0);          
      }
      
      int construct(int arr[], int ss, int se, int si) {
        if (ss == se) {
          st[si] = arr[ss];
          return arr[ss];
        }

        int mid = getMid(ss, se);
        st[si] = (int) sum(construct(arr, ss, mid, si * 2 + 1), 
                construct(arr, mid + 1, se, si * 2 + 2));
        return st[si];
      }

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

    static long sum(long a, long b) {
        return (a + b) % MOD;
    }
    
  public static long power(long a, long n) {
    if (n < 0) {
      return power(power(a, MOD - 2), -n);
    }
    if (n == 0) {
      return 1;
    }
    if (n == 1) {
      return a;
    }

    long r = 1;
    for (; n > 0; n >>= 1, a = (a*a) % MOD) {
      if ((n & 1) > 0) {
        r = (r*a) % MOD;
      }
    }
    return r;
  }
    
    
  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 a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    int q = Integer.parseInt(st.nextToken());

    if (b > 0) {
      int[] pw = new int[n+1];
      
        long coef = (MOD - mul(b, power(a, MOD - 2))) % MOD;
        pw[0] = 1;
        for (int i = 1; i <= n; i++) {
            pw[i] = (int) mul(pw[i - 1], coef);
        }
      
      int[] p = new int[n];
      st = new StringTokenizer(br.readLine());

      for (int i = 0; i < n; i++) {
        int cItem = Integer.parseInt(st.nextToken());
        p[i] = (int) mul(pw[i], cItem);
      }

      SegmentTree tree = new SegmentTree(p.length);
      tree.construct(p);
      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());
          if (op == 1) {
              tree.updateValue(p, l, (int) mul(pw[l], r));
          } else {
              long ans = tree.getSum(l, r);
          bw.write( ans == 0 ? "Yes" : "No");
          bw.write("n");
          }
      }
    } else {
      int[] c = new int[n];
      st = new StringTokenizer(br.readLine());

      for (int i = 0; i < n; i++) {
        int cItem = Integer.parseInt(st.nextToken());
        c[i] = cItem;
      }
      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());
          if (op == 1) {
              c[l] = r;
          } else {
              long ans = c[l];
          bw.write( ans == 0 ? "Yes" : "No");
          bw.write("n");
          }
      }
    }
    
    bw.close();
    br.close();
  }
}

Problem solution in C++ programming.

#include <iostream>
#include <vector>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cstdio>
#include <queue>
#include <set>
#include <map>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const int maxn = 110000;
const i64 P = 1000000000 + 7;

i64 deg(i64 x, i64 d) {
    d %= P - 1;
    if (d < 0) d += P - 1;
    i64 y = 1;
    while (d) {
        if (d & 1) y *= x, y %= P;
        x *= x, x %= P;
        d /= 2;
    }
    return y;
}

i64 f[maxn], d[maxn], a[maxn];

void add(i64 &x, i64 y) {
    x += y; x %= P;
}

void fadd(int i, i64 x) {
    for (; i < maxn; i |= i + 1) add(f[i], x);
}

i64 fsum(int i) {
    i64 s = 0;
    for (; i >= 0; i &= i + 1, --i) add(s, f[i]);
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "rt", stdin);
#endif

    int n, q;
    i64 A, B;
    cin >> n >> A >> B >> q;
    i64 z = -B * deg(A, -1) % P;
//    cerr << z << 'n';
    d[0] = 1;
    forn(i, n) {
        cin >> a[i];
//        a[i] *= d[i]; a[i] %= P;
        d[i + 1] = d[i] * z % P;
    }
    forn(i, n) fadd(i, a[i] * d[i]);
    forn(i, q) {
        int t;
        cin >> t;
        if (t == 1) {
            int i;
            i64 x;
            cin >> i >> x;
//            --i;
            fadd(i, (x - a[i]) * d[i]);
            a[i] = x;
        } else {
            int l, r;
            cin >> l >> r;
//            --l;
            ++r;
            i64 res = fsum(r - 1) - fsum(l - 1);
            res %= P;
            if (!z) res = a[l];
//            cerr << res << 'n';
            cout << (res ? "No" : "Yes") << 'n';
        }
    }

#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.n";
#endif
    return 0;
}

Problem solution in C programming.

#include<stdio.h>
#define MAXN 100000
#define MOD 1000000007
int n, q, type, u, v;
long long a[MAXN+2], c1, c2, x, it[MAXN*4 + 2];
long long modPow(long long x, long long y)
{
    long long res = 1;
    while(y)
    {
        if( y & 1 )
        {
            res = res * x % MOD;
        }
        y >>= 1;
        x = x * x % MOD;
    }
    return res;
}
void build(int node, int lef, int rig)
{
    if( lef == rig )
    {
        it[node] = a[lef];
        return;
    }
    int lnode = ( node << 1 );
    int rnode = ( ( node << 1 ) | 1 );
    int mid = ( ( lef + rig ) >> 1 );
    build(lnode, lef, mid);
    build(rnode, mid+1, rig);
    int len = mid - lef + 1;
    it[node] = ( it[lnode] + it[rnode] * modPow(x, len) ) % MOD;
}
void update(int node, int lef, int rig, int pos, long long val)
{
    if( lef > pos || rig < pos )
    {
        return;
    }
    if( lef == rig )
    {
        it[node] = a[pos] = val;
        return;
    }
    int lnode = ( node << 1 );
    int rnode = ( ( node << 1 ) | 1 );
    int mid = ( ( lef + rig ) >> 1 );
    update(lnode, lef, mid, pos, val);
    update(rnode, mid+1, rig, pos, val);
    int len = mid - lef + 1;
    it[node] = ( it[lnode] + it[rnode] * modPow(x, len) ) % MOD;
}
long long get(int node, int lef, int rig, int l, int r)
{
    if( lef > r || rig < l )
    {
        return 0;
    }
    if( lef >= l && rig <= r )
    {
        return it[node] * modPow(x, lef - l) % MOD;
    }
    int lnode = ( node << 1 );
    int rnode = ( ( node << 1 ) | 1 );
    int mid = ( ( lef + rig ) >> 1 );
    return ( get(lnode, lef, mid, l, r) + get(rnode, mid+1, rig, l, r) ) % MOD;
}
int main()
{
    scanf("%d %lld %lld %d", &n, &c1, &c2, &q);
    for( int i = 0 ; i < n ; ++i )
    {
        scanf("%lld", a + i);
    }
    x = ( MOD - c2 ) * modPow(c1, MOD - 2) % MOD;
    build(1, 0, n-1);
    while( q --> 0 )
    {
        scanf("%d", &type);
        if( type == 1 )
        {
            scanf("%d %lld", &u, &c1);
            update(1, 0, n-1, u, c1);
        }
        else
        {
            scanf("%d %d", &u, &v);
            long long tmp = get(1, 0, n-1, u, v);
            if( get(1, 0, n-1, u, v) == 0 )
            {
                printf("Yesn");
            }
            else
            {
                printf("Non");
            }
        }
    }
    return 0;
}