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 Operations on an array problem solution

YASH PAL, 31 July 2024
In this HackerEarth Operations on an array problem solution, You are given an array of n elements and an integer x. You must perform the following types of operations on the array:
Find the index of the kth occurrence of x in the range l to r (both inclusive). If there are no indexes that satisfy the condition, then print -1.
Update the value that is present at the given index.
For each query of type 1, print the index of the kth occurrence of x.
HackerEarth Operations on an array problem solution

HackerEarth Operations on an array problem solution.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

const int N = 1000000 + 1;
int arr[N];
struct BIT{//use one based indexing
int N;
vector<int> bit;

void init(int n){
bit.clear();
N = n + 9;
bit.assign(n + 10, 0);
}

void update(int idx, int val){
while(idx <= N){
bit[idx] += val;
idx += idx & -idx;
}
}

int pref(int idx){
int ans = 0;
while(idx > 0){
ans += bit[idx];
idx -= idx & -idx;
}
return ans;
}

int rsum(int l, int r){
return pref(r) - pref(l - 1);
}

int kthOrder(int k){
if(pref(N - 1) < k){
return -1;
}
int cur = 0,sum = 0, ExtraSize = N;
int ln = log2(ExtraSize);
for(int i = ln;i >= 0 ; --i){
int temp = cur + (1 << i);
if((temp < ExtraSize) && (sum + bit[temp]) < k){
cur = temp;
sum += bit[temp];
}
}
return cur + 1;
}

//one based indexing
int lower_bound(int val){
return (pref(val - 1) + 1);
}
//one based indexing
int upper_bound(int val){
return (pref(val) + 1);
}
}bt;
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n,x;
cin >> n >> x;
bt.init(n);
for(int i = 1;i <= n;i++){
cin >> arr[i];
if(arr[i] == x){
bt.update(i,1);
}
}
int q;
cin >> q;
while(q--){
int type;
cin >> type;
if(type == 1){
int l,r,k;
cin >> l >> r >> k;
k += bt.pref(l - 1);
if(k > bt.pref(r)){
cout << "-1n";;
continue;
}
cout << bt.kthOrder(k) << "n";
}else{
int l,val;
cin >> l >> val;
if(arr[l] == x){
bt.update(l,-1);
}
if(val == x){
bt.update(l,1);
}
arr[l] = val;
}
}
}

Second solution

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> os;
typedef long long ll;
const int maxn = 1e6 + 14, mod = 1e9 + 7;

int n, a[maxn], x;
int pos(int p){
auto s = os.lower_bound(p);
if(s == os.end())
return os.size();
return os.order_of_key(p);
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> x;
for(int i = 0; i < n; i++){
cin >> a[i];
if(a[i] == x)
os.insert(i);
}
int q;
cin >> q;
while(q--){
int t;
cin >> t;
if(t == 1){
int l, r, k;
cin >> l >> r >> k;
l--, k--;
if(pos(l) == n || pos(l) + k >= pos(r))
cout << "-1n";
else
cout << *os.find_by_order(pos(l) + k) + 1 << 'n';
}
else{
int i, v;
cin >> i >> v;
i--;
if(a[i] == x)
os.erase(i);
a[i] = v;
if(a[i] == x)
os.insert(i);
}
}
}
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