🧩 Problem 1: Count Divisible Triplets
You're given:
An integer array arr of length n
An integer div
Your task is to count the number of triplets (i, j, k) such that:
0 ≤ i < j < k < n
(arr[i] + arr[j] + arr[k]) % div == 0
Return the total number of such triplets.
🧩 Problem 2: Signal Activation and Processor Cost
You are given a binary signal array of length n, where all elements are initially set to 0. This array represents inactive signals.
You are also given a ping array of length n which contains a permutation of the integers from 0 to n - 1. This array represents a sequence of signal activations.
🔧 Activation and Processor Behavior
When the processor receives a ping for signal i (i.e., ping[k] == i), it activates the i-th signal by setting signal[i] = 1.
After each activation, the processor performs a sequence of swap operations, with the following rule:
For every index j from 0 to n - 2, if signal[j] == 1 and signal[j+1] == 0, the processor swaps signal[j] and signal[j+1].
The processor continues to do this until no more such swaps are possible.
Each individual swap operation costs 1 unit.
🎯 Task
For each ping (activation), return the total number of swap operations (i.e., the cost) performed by the processor after that activation.
#include <iostream>
#include <vector>
#include <set>
using namespace std;
class SegmentTree {
int size;
vector<int> tree;
void update(int node, int l, int r, int idx, int val) {
if (l == r) {
tree[node] = val;
return;
}
int mid = (l + r) / 2;
if (idx <= mid)
update(2 * node, l, mid, idx, val);
else
update(2 * node + 1, mid + 1, r, idx, val);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
int query(int node, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return 0;
if (ql <= l && r <= qr) return tree[node];
int mid = (l + r) / 2;
return query(2 * node, l, mid, ql, qr) + query(2 * node + 1, mid + 1, r, ql, qr);
}
public:
SegmentTree(int n) : size(n), tree(4 * n, 0) {}
void update(int idx, int val) {
update(1, 0, size - 1, idx, val);
}
int query(int l, int r) {
return query(1, 0, size - 1, l, r);
}
};
vector<int> optimizedWithSegmentTree(const vector<int>& queries) {
int n = queries.size();
SegmentTree seg(n);
set<int> zeroSet;
vector<int> result;
for (int i = 0; i < n; ++i)
zeroSet.insert(i);
int ones=0;
for (int idx : queries) {
zeroSet.erase(idx-1);
seg.update(idx-1, 1);
ones++;
if (zeroSet.empty()) {
result.push_back(1);
} else {
int rightmostZero = *zeroSet.rbegin();
result.push_back(ones - seg.query(rightmostZero + 1, n - 1) + 1);
}
}
return result;
}
int main() {
vector<int> queries = {2, 1, 3, 4, 6, 5};
// 0 0 0 0 0 0
// 1 1 0 0 0 0
// 1 1 1 0 0 0
// 1 1 1 1 0 0
// 1 1 1 1 0 1
vector<int> result = optimizedWithSegmentTree(queries);
for (int x : result)
cout << x << " ";
cout << endl;
return 0;
}For second question, I was able to comeup with this solution after OA completion.
In OA, I passed all test cases for 1st Question (15/15).
For 2nd Question, Brute Force (9/15).
