Set Size | CodeChef Starters 232 | Codechef Contest solutions

🚀 In this video, we solve the "Set Size" problem from a CodeChef Contest.

💡 Problem:
Given an array A, for each query X:
Construct set S = {Ai + j | 1 ≤ i ≤ N, 1 ≤ j ≤ X}

👉 Find:
Number of distinct elements in S

---

🧠 Key Observation:
Each element forms a range:
[Ai + 1 → Ai + X]

So problem becomes:
👉 Count size of UNION of intervals

---

🔥 Trick Used:
- Sort array
- Compute gaps between elements
- Use formula:
sum(min(gap, X))

- Add a dummy large gap (1e9+10) to handle "+X"

---

⚡ Optimization:
- Prefix Sum on gaps
- Binary Search for each query

---

⏱ Time Complexity:
O((N + Q) log N)

💻 Language:
C++

---

🔥 Concepts Covered:
- Greedy
- Prefix Sum
- Binary Search
- Interval Merging Trick

---

🎯 Perfect for:
- CodeChef Contests
- Competitive Programming
- Interview Preparation

---

👍 Like | 💬 Comment | 🔔 Subscribe for more CP content

#CodeChef #CompetitiveProgramming #PrefixSum #BinarySearch #Algorithms #Cplusplus

Видео Set Size | CodeChef Starters 232 | Codechef Contest solutions канала AlgoTribe