Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

HackerEarth Greatest common divisor problem solution

YASH PAL, 31 July 2024
In this HackerEarth Greatest common divisor problem solution, you are given array A. There are 4 types of operations associated with it:
  1. l r x, for each i ∈ [l, r] replace ai with the value of x.
  2. l r x, for each i ∈ [l, r] replace ai with the value of the gcd(ai, x) function.
  3. l r, print the value of max ai, l ≤ i ≤ r.
  4. l r, print the value of al + al+1 + … + ar.
The greatest common divisor (gcd(a, b)) of two positive integers a and b is equal to the biggest integer d such that both integers a and b are divisible by d.
HackerEarth Greatest common divisor problem solution

HackerEarth Greatest common divisor problem solution.

#include<bits/stdc++.h>
using namespace std;

const int MAX_N = 2e5 + 111;

struct node{
long long sum;
int element;
int mx;
int lz;
int l, r;

node(){
element = -1;
sum = 0;
mx = 0;
lz = -1;
l = 0;
r = 0;
}

node(int value){
element = value;
sum = value;
mx = value;
}

};

node t[4 * MAX_N];
int a[MAX_N];
int n, q;

inline node merge(node a, node b){
node c = node();

c.sum = a.sum + b.sum;

c.mx = max(a.mx, b.mx);
if(a.element == b.element && a.element > 0)
c.element = a.element; else c.element = -1;

return c;
}

void build(int v,int tl,int tr){
if(tl == tr){
t[v] = node(a[tl]);
t[v].l = t[v].r = tl;
return;
}
int tm = (tl + tr) >> 1,
L = v << 1,
R = L | 1;
build(L, tl, tm);
build(R, tm + 1, tr);
t[v] = merge(t[L],t[R]);
t[v].l = tl;
t[v].r = tr;
}

inline void assignment(int v,int val){
t[v].lz = val;
t[v].sum = (t[v].r - t[v].l + 1) *1ll* val;
t[v].mx = val;
t[v].element = val;
}

inline void push(int v,int L,int R){
if(t[v].lz != -1){
if(t[v].l != t[v].r){
assignment(L, t[v].lz);
assignment(R, t[v].lz);
int l = t[v].l,
r = t[v].r;
t[v] = merge(t[L],t[R]);
t[v].l = l;
t[v].r = r;
}
t[v].lz = -1;
}
}

void update1(int v,int l,int r,int val){
if(t[v].l > r || t[v].r < l)return;
if(t[v].l >= l && t[v].r <= r){
assignment(v, val);
return;
}
int L = v << 1,
R = L | 1;
push(v, L, R);
update1(L, l, r, val);
update1(R, l, r, val);
int l_ = t[v].l,
r_ = t[v].r;
t[v] = merge(t[L], t[R]);
t[v].l = l_;
t[v].r = r_;
}

void update2(int v,int l,int r,int val){
if(t[v].l > r || t[v].r < l)return;
if(t[v].l >= l && t[v].r <= r && t[v].element > 0){
assignment(v, __gcd(val, t[v].element));
return;
}
int L = v << 1,
R = L | 1;
push(v, L, R);
update2(L, l, r, val);
update2(R, l, r, val);
int l_ = t[v].l,
r_ = t[v].r;
t[v] = merge(t[L], t[R]);
t[v].l = l_;
t[v].r = r_;
}

node NULL_;

node get(int v,int l,int r){
if(t[v].l > r || t[v].r < l)return NULL_;
int L = v << 1,
R = L | 1;
push(v, L, R);
if(t[v].l >= l && t[v].r <= r)return t[v];
int tm = (t[v].l + t[v].r) >> 1;
if(r <= tm)return get(L, l, r);
if(l > tm)return get(R, l, r);
node ans1 = get(L, l, r),
ans2 = get(R, l, r);
node ans = merge(ans1, ans2);
return ans;
}

int main(){

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

// freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

int n, q;
cin >> n >> q;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}

build(1, 1, n);

while(q-->0){
int type, l, r;
cin >> type >> l >> r;
if(type == 1){
int x;
cin >> x;
update1(1, l, r, x);
}else
if(type == 2)
{
int x;
cin >> x;
update2(1, l, r, x);
}else{
if(type == 3)cout << get(1, l, r).mx << 'n';
else cout << get(1, l, r).sum << 'n';
}
}

return 0;
}
coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes