Skip to content
Programming101
Programmingoneonone

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • 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
Programming101
Programmingoneonone

Learn everything about programming

HackerEarth Reunion of 1’s problem solution

YASH PAL, 31 July 2024
In this HackerEarth Reunion of 1’s problem solution, You are given a string of size n consisting of 0s and/or 1s. You have to perform total k queries and there are two types of queries possible:
  1. “1” (without quotes): Print length of the longest sub-array which consists of all ‘1’.
  2. “2 X” (without quotes): where X is an integer between 1 to n. In this query, you will change character at the Xth position to ‘1’ (It is possible that the character at i-th position was already ‘1’).
HackerEarth Reunion of 1's problem solution

HackerEarth Reunion of 1’s problem solution.

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

#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); i--)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> void setmin(T& a, T val) {if (a > val) a = val;}
template<class T> void setmax(T& a, T val) {if (a < val) a = val;}
void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}

int a[1000005],keep[1000005],size[1000005];
int ans;
int root(int i)
{
while(keep[ i ] != i)
i = keep[ i ];

return i;
}
void unio(int A,int B)
{
int AA = root(A);
int BB = root(B);
if(size[AA] < size[BB ])
{
keep[ AA ] = keep[BB];
size[BB] += size[AA];
}
else
{
keep[ BB ] = keep[AA];
size[AA] += size[BB];
}

}
bool find(int A,int B)
{
if( root(A)==root(B) )
return true;
else
return false;
}
void update(int num)
{
if(a[num])return ;
a[num] = 1;
size[num] = 1;
keep[num] = num;

if(a[num-1])
unio(num,num-1);
if(a[num+1])
unio(num,num+1);

ans = max(ans,size[root(num)]);
}

int main() {
ios_base::sync_with_stdio(0); cin.tie(0);

ll n,q;cin>>n>>q;
string str;cin>>str;

FOR(i,0,str.length())
{
if(str[i]=='1')
{
update(i+1);
}
}

while(q--)
{
int type;cin>>type;
if(type==1)
cout<<ans<<"n";
else
{
int num;cin>>num;
update(num);
}

}

return 0;
}

Second solution

#include<bits/stdc++.h>
using namespace std;
int n,q,maxx;
int par[100005],size[100005];
int find(int x)
{
if(x==par[x])return par[x];
return par[x]=find(par[x]);
}
void unionset(int a,int b)
{
int para=find(a);
int parb=find(b);
if(para==parb)return;
if(size[para]<size[parb])
{
par[para]=parb;
size[parb]+=size[para];
maxx=max(maxx,size[parb]);
}
else
{
par[parb]=para;
size[para]+=size[parb];
maxx=max(maxx,size[para]);
}
}
int main()
{
cin>>n>>q;
string s;
cin>>s;s="0"+s+"0";
for(int i=1;i<=n;i++)
{
if(s[i]=='1')
{
size[i]=1;par[i]=i;maxx=1;
}
}
for(int i=1;i<=n;i++)
{
if(s[i]=='1')
{
if(s[i-1]=='1')unionset(i-1,i);
//if(s[i+1]=='1')unionset(i,i+1);
}
}
while(q--)
{
int type;
cin>>type;
if(type==1)cout<<maxx<<"n";
else
{
int ind;
cin>>ind;
if(s[ind]=='1')continue;
s[ind]='1';size[ind]=1;par[ind]=ind;maxx=max(maxx,1);
if(s[ind-1]=='1'){unionset(ind-1,ind);}
if(s[ind+1]=='1')unionset(ind,ind+1);
}
}
return 0;
}
coding problems solutions

Post navigation

Previous post
Next post
  • Automating Image Format Conversion with Python: A Complete Guide
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
How to download udemy paid courses for free

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