[1]📘 Difference Array for Efficient Range Updates
🔍 Definition
A Difference Array is a technique used to perform multiple range update operations on an array efficiently
in O(1) time per update.
Given an array arr[0..n-1], its difference array d is defined as:
d[0] = arr[0]
d[i] = arr[i] - arr[i-1] for 1 <= i < n
⚙️Key Operations
✅ Initialization (initDiffArray)
d[0] = arr[0]
for i from 1 to n-1:
d[i] = arr[i] - arr[i-1]
✅ Range Update in O(1) (update)
To apply +x to all elements in the range [l, r]:
d[l] += x
d[r + 1] -= x
✅ Construct Final Array (printArray)
To get the updated array from the difference array:
arr[0] = d[0]
for i from 1 to n-1:
arr[i] = arr[i-1] + d[i]
🧮 Example
Initial Array: arr = [2, 5, 7, 9, 6]
Difference Array: d = [2, 3, 2, 2, -3]
Apply Update: update(1, 3, 4)
→ d = [2, 7, 2, 2, -7]
Rebuild Array:
arr = [2, 9, 11, 13, 6]
💻 C++ Implementation
vector<int> initDiffArray(vector<int> &arr) {
int n = arr.size();
vector<int> d(n + 1, 0);
d[0] = arr[0];
for (int i = 1; i < n; i++) {
d[i] = arr[i] - arr[i - 1];
return d;
void update(vector<int> &d, int l, int r, int x) {
d[l] += x;
d[r + 1] -= x;
void printArray(vector<int> &arr, vector<int> &d) {
for (int i = 0; i < arr.size(); i++) {
if (i == 0)
arr[i] = d[i];
else
arr[i] = d[i] + arr[i - 1];
cout << arr[i] << " ";
cout << endl;
🧾 Time & Space Complexity
update(l, r, x): O(1)
printArray(): O(n)
Space: O(n) for the difference array
https://leetcode.com/problems/zero-array-transformation-i/description/
[2] Modulo Power Calculation
long long modulopower(long long n){
if(n==1){
return 2;
if(n==0){
return 1;
if(n&1){
return (2LL * modulopower(n / 2) % MOD * modulopower(n / 2) % MOD) % MOD;
else{
return (1LL * modulopower(n / 2) % MOD * modulopower(n / 2) % MOD) % MOD;
[3] Multiset
-Basic Syntax
multiset<int> ms;
-Insertion
ms.insert(10); // Inserts 10
ms.insert(10); // Duplicates allowed
-Iteration
for (int x : ms)
cout << x << " ";
for (auto it = ms.begin(); it != ms.end(); ++it)
cout << *it << " ";
-Deletion
ms.erase(ms.find(10)); // Deletes one occurrence
ms.erase(10); // Deletes ALL occurrences
-Search
auto it = ms.find(10);
if (it != ms.end()) {
cout << "Found";
-Count Duplicates
int c = ms.count(10); // Number of times 10 appears
-Bounds
ms.lower_bound(x); // First element >= x
ms.upper_bound(x); // First element > x
-Size & Emptiness
ms.size(); // Total number of elements
ms.empty(); // Returns true if empty
-Clear All Elements
ms.clear(); // Empties the multiset
-Reverse Iteration
for (auto it = ms.rbegin(); it != ms.rend(); ++it)
cout << *it << " ";
-Initialize with Elements
multiset<int> ms = {5, 1, 3, 3, 7};
-Custom Comparator (Descending Order)
multiset<int, greater<int>> ms;
-Example Use Case: Ticket Problem
multiset<int> prices = {5, 3, 7, 8, 5};
int max_price = 6;
auto it = prices.upper_bound(max_price);
if (it == prices.begin()) cout << -1;
else {
--it;
cout <<
*it;prices.erase(it
);
-Tips
Prefer multiset when you need:
- Duplicates allowed
- Sorted elements
- Logarithmic insert/delete/search
[4] Weighted Median
If the cost for all element is the same, then the minimum cost is when
all numbers converge at the median.
Since the cost is not the same, we need to find a weighted median.
To find a weighted median, we sort elements, "repeating" each element
based on its weight.
For [1,3,5,2], [2,3,1,4] case, the repeated array looks like this (median
is in bold): [1,1,2,2,2,2,3,3,3,5].
We do not need to actually generate that repeated array, we can just
simulate it.
We find the total weight (10), aggregate the current weight going from
one side, and stop when current >= total / 2.
📌 Use Cases
Minimize total weighted absolute deviation:
minimize ∑i∣x−ai∣⋅wi\text{minimize } \sum_{i} |x - a_i| \cdot
w_iminimize i∑∣x−ai∣⋅wi
Problems like:
o Min-cost to make all elements equal with weights.
o Clustering, statistics, and resource allocation.
⚙️ Steps to Compute Weighted Median
1. Input: Array of pairs (value, weight) → vector<pair<long long, long
long>>.
2. Sort array by value.
3. Compute total weight W.
4. Traverse and accumulate weights until ≥ W / 2.
5. The current value is the weighted median.
🧪 Example
cpp
CopyEdit
values: [1, 3, 6]
weights: [2, 4, 3]
total weight = 9
Cumulative weights:
1 → 2
3 → 6 (>= 4.5) → weighted median = 3
📎 C++ Snippet
long long weighted_median(vector<pair<long long, long long>>& arr) {
sort(arr.begin(), arr.end()); // sort by value
long long total_weight = 0;
for (auto& p : arr) total_weight += p.second;
long long cumulative = 0;
for (auto& p : arr) {
cumulative += p.second;
if (cumulative >= (total_weight + 1) / 2) {
return p.first; // weighted median
}
}
return -1; // should not happen
🕒 Time Complexity
O(n log n) – due to sorting.
O(n) – for cumulative sum.
[5]a&-1=a;
[6] https://www.geeksforgeeks.org/program-nth-catalan-number/
[7] Lis using binary search
vector<int> lis;
for (int x : arr) {
auto it = lower_bound(lis.begin(), lis.end(), x);
if (it == lis.end()) lis.push_back(x);
else *it = x;
}
}
[8]
Given an array of integers nums and an integer k, return the number of subarrays of nums where
the bitwise AND of the elements of the subarray equals k.
class Solution
{
public:
long long countSubarrays(vector<int> &nums, int k)
{
return atLeastK(nums, k) - atLeastK(nums, k +1);
}
long long atLeastK(vector<int>& nums, int k){
long long ans = 0;
vector<int> temp(32, 0);
int l = 0;
for (int r = 0; r < nums.size(); r++)
{
for (int i = 0; i < 32; i++)
{
if ((1 << i) & nums[r])
{
temp[i]++;
}
}
while ((r - l + 1) > 0 && calc(temp, r - l + 1) < k)
{
for (int i = 0; i < 32; i++)
{
if ((1 << i) & nums[l])
{
temp[i]--;
}
}
l++;
}
ans += (r - l + 1);
}
return ans;
}
//function to calculate the AND from frequency vector
int calc(vector<int>& temp, int w){
int ans = 0;
for (int i = 0; i < 32;i++){
if(temp[i]==w)
ans += (1 << i);
}
return ans;
}
};
Here we are storing freq of each bit when we want to shrink the
window we simply convert our end ouput for window by considering two
cases
1. If freq of bit is==w than it wil be 1 for our result bit
2. If freq of bit is not equal to w than it will be 0 for our
result bit
[8]ReRooting in Tree is used when you already find value corresponding to root node and you want
to find values corresponding to other node in o(n) tc than we used this technique
https://leetcode.com/problems/sum-of-distances-in-tree/
class Solution {
public:
int dfs(vector<vector<int>>&adj,vector<int>&count,int
curr_node,int& root,int parent,int depth){
int total_node=1;
root+=depth;
for(auto it:adj[curr_node]){
if(it==parent)continue;
total_node+=dfs(adj,count,it,root,curr_node,depth+1);
}
count[curr_node]=total_node;
return total_node;
}
void
DFS(vector<vector<int>>&adj,vector<int>&count,vector<int>&result,
int curr_node,int parent){
for(auto it:adj[curr_node]){
if(it==parent)continue;
result[it]=result[curr_node]-(count[it])+
(count.size()-count[it]);
DFS(adj,count,result,it,curr_node);
}
}
vector<int> sumOfDistancesInTree(int n, vector<vector<int>>&
edges) {
vector<int>count(n,0);
vector<int>result(n,0);
vector<vector<int>>adj(n);
for(auto edge:edges){
int u=edge[0];
int v=edge[1];
adj[u].push_back(v);
adj[v].push_back(u);
}
int root=0;
dfs(adj,count,0,root,-1,0);
result[0]=root;
DFS(adj,count,result,0,-1);
return result;
}
};
The Formula:
result[child] = result[parent] - count[child] + (n - count[child])
Why this works:
When moving root from parent to child:
o All nodes in child's subtree get closer by 1 → decrease total sum by
count[child]
o All other nodes get farther by 1 → increase total sum by n - count[child]
[9]
🧠 What is the Sieve of Eratosthenes?
The Sieve of Eratosthenes is a method to generate all prime numbers up to a given number
n using the idea of eliminating multiples of each prime number starting from 2.
It is based on the fact that:
Every composite number has a prime factor less than or equal to its square root.
🪜 Step-by-step Explanation
Let’s say we want to find all prime numbers from 1 to n = 30.
Step 1: Create a boolean array
Create a boolean array isPrime[0...n] and initialize all values to true.
Set isPrime[0] = false and isPrime[1] = false because 0 and 1 are not prime.
text
CopyEdit
Index: 0 1 2 3 4 5 6 7 8 9 10 ...
isPrime: [ F, F, T, T, T, T, T, T, T, T, T ... ]
Step 2: Start with the first prime number (2)
For every number p from 2 to √n:
If isPrime[p] == true, mark all multiples of p (starting from p*p) as false.
Why start from p*p?
Because all smaller multiples (like 2p, 3p, ...) will already have been marked by smaller
primes.
Step 3: Mark multiples
Let’s apply it step-by-step:
p = 2:
Mark 4, 6, 8, 10, ..., 30 as not prime.
p = 3:
Mark 9, 12, 15, ..., 30 as not prime.
p = 4:
Already marked as not prime, so skip.
p = 5:
Mark 25, 30 as not prime.
Now stop — because p*p = 6*6 = 36 > 30.
Step 4: Collect remaining primes
All numbers i such that isPrime[i] == true are primes.
text
CopyEdit
Result: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29
🧮 Time and Space Complexity
Aspect Value
Time Complexity O(n log log n)
Space Complexity O(n)
It is much faster than checking each number one by one for primality.
✅ C++ Implementation
vector<bool> sieve(int n) {
vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;
for (int p = 2; p * p <= n; p++) {
if (isPrime[p]) {
for (int i = p * p; i <= n; i += p) {
isPrime[i] = false;
}
}
}
return isPrime; // true => prime, false => not prime
}
🧑🏫 Summary
Simple yet efficient algorithm for generating primes.
Uses the principle of eliminating multiples.
Extremely useful in competitive programming and number theory problems.
[10] In string question try to find FIFO or LIFO property if nothing works
