•  » » 5 days ago, # ^ |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } Two pointers is really an easy and effective technique that is typically used for searching pairs in a sorted array. Given a sorted array A (sorted in ascending order), having N integers, find if there exists any pair of elements (A[i], A[j]) such that their sum is equal to X. Illustration :A[] = {10, 20, 35, 50, 75, 80} X = =70 i = 0 j = 5 A[i] + A[j] = 10 + 80 = 90 Since A[i] + A[j] > X, j-- i = 0 j = 4 A[i] + A[j] = 10 + 75 = 85 Since A[i] + A[j] > X, j-- i = 0 j = 3 A[i] + A[j] = 10 + 50 = 60 Since A[i] + A[j] < X, i++ i = 1 j = 3 m A[i] + A[j] = 20 + 50 = 70 Thus this signifies that Pair is Found.Let us do discuss the working of two pointer algorithm in brief which is as follows. The algorithm basically uses the fact that the input array is sorted. We start the sum of extreme values (smallest and largest) and conditionally move both pointers. We move left pointer ‘i’ when the sum of A[i] and A[j] is less than X. We do not miss any pair because the sum is already smaller than X. Same logic applies for right pointer j. Code#include using namespace std; bool isPairSum(int A[], int N, int X) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { // as equal i and j means same element if (i == j) continue; // pair exists if (A[i] + A[j] == X) return true; // as the array is sorted if (A[i] + A[j] > X) break; } } // No pair found with given sum. return false; } // Driver code int main() { int arr[] = { 2, 3, 5, 8, 9, 10, 11 }; int val = 17; int arrSize = *(&arr + 1) - arr; sort(arr, arr + arrSize); // Sort the array // Function call cout << isPairSum(arr, arrSize, val); return 0; } Time Complexity: O(n2). Auxiliary Space: O(1)Lets solve EDU problem:step 1:Merging Arrays Code#include using namespace std; int n, m; vector v1, v2, v3; int main() { scanf("%d%d", &n, &m); v1.resize(n); for (auto &x : v1) scanf("%d", &x); v2.resize(m); for (auto &x : v2) scanf("%d", &x); int p1 = 0, p2 = 0; while (p1 < n || p2 < m) { if (p1 == n) v3.push_back(v2[p2++]); else if (p2 == m) v3.push_back(v1[p1++]); else if (v1[p1] < v2[p2]) v3.push_back(v1[p1++]); else v3.push_back(v2[p2++]); } for (auto x : v3) printf("%d ", x); return 0; } Number of Smaller Code#include using namespace std; int n, m; vector v1, v2; int main() { scanf("%d%d", &n, &m); v1.resize(n); for (auto &x : v1) scanf("%d", &x); v2.resize(m); for (auto &x : v2) scanf("%d", &x); int p1 = 0; for (auto x : v2) { if (x <= v1[0]) { printf("0 "); continue; } while (p1 < n && v1[p1] < x) ++p1; printf("%d ", p1); } return 0; } Number of Equal Code#include using namespace std; int n, m; vector v1, v2; int main() { scanf("%d%d", &n, &m); v1.resize(n); for (auto &x : v1) scanf("%d", &x); v2.resize(m); for (auto &x : v2) scanf("%d", &x); int p1 = 0, p2 = 0; long long ans = 0; while (p1 < n && p2 < m) { if (v1[p1] == v2[p2]) { int num1 = 1, num2 = 1; ++p1; while (p1 < n && v1[p1] == v1[p1 - 1]) ++num1, ++p1; ++p2; while (p2 < m && v2[p2] == v2[p2 - 1]) ++num2, ++p2; ans += 1ll * num1 * num2; } else if (v1[p1] < v2[p2]) { ++p1; while (p1 < n && v1[p1] == v1[p1 - 1]) ++p1; } else if (v1[p1] > v2[p2]) { ++p2; while (p2 < m && v2[p2] == v2[p2 - 1]) ++p2; } } printf("%lld\n", ans); return 0; } step 2:Segment with Small Sum Code#include using namespace std; int n; long long s; vector v; int main() { scanf("%d%lld", &n, &s); v.resize(n); for (auto &x : v) scanf("%d", &x); int l = 0, ans = 0; long long sum = 0; for (int i = 0; i < v.size(); ++i) { sum += v[i]; while (sum > s) { sum -= v[l++]; } ans = max(ans, i - l + 1); } printf("%d\n", ans); return 0; } Segment with Big Sum Code#include using namespace std; int n; long long s; vector v; int main() { scanf("%d%lld", &n, &s); v.resize(n); for (auto &x : v) scanf("%d", &x); int l = 0, ans = n + 1; long long sum = 0; for (int i = 0; i < v.size(); ++i) { sum += v[i]; if (sum < s) continue; while (sum >= s) { sum -= v[l++]; } ans = min(ans, i - l + 2); } if (ans > n) ans = -1; printf("%d\n", ans); return 0; } Number of Segments with Small Sum Code#include using namespace std; int n; long long s; vector v; vector v2; int main() { scanf("%d%lld", &n, &s); v.resize(n); for (auto &x : v) scanf("%d", &x); int l = 0; long long sum = 0, ans = 0; for (int i = 0; i < v.size(); ++i) { sum += v[i]; while (sum > s) sum -= v[l++]; ans += i - l + 1; } printf("%lld\n", ans); return 0; } Number of Segments with Big Sum Code#include using namespace std; int n; long long s; vector v; int main() { scanf("%d%lld", &n, &s); v.resize(n); for (auto &x : v) scanf("%d", &x); int l = 0; long long sum = 0, ans = 0; for (int i = 0; i < v.size(); ++i) { sum += v[i]; while (sum >= s) sum -= v[l++]; ans += l; } printf("%lld\n", ans); return 0; } Segments with Small Set Code#include using namespace std; const int MAXN = 1e5 + 5; int n, k; vector v; int Tms[MAXN]; int main() { scanf("%d%d", &n, &k); v.resize(n); for (auto &x : v) scanf("%d", &x); long long ans = 0; int l = 0, num = 0; for (int i = 0; i < n; ++i) { if (!Tms[v[i]]++) { if (++num > k) { while (true) if (--Tms[v[l++]] == 0) break; } } ans += i - l + 1; } printf("%lld\n", ans); return 0; } Segments with Small Spread Code 1#include using namespace std; int n; long long k; vector v; deque Mn, Mx; int main() { scanf("%d%lld", &n, &k); v.resize(n); for (auto &x : v) scanf("%lld", &x); long long ans = 0; int l = 0; for (int i = 0; i < n; ++i) { while (!Mn.empty() && v[Mn.back()] > v[i]) Mn.pop_back(); while (!Mx.empty() && v[Mx.back()] < v[i]) Mx.pop_back(); Mn.push_back(i), Mx.push_back(i); while (v[Mx.front()] - v[Mn.front()] > k) { l++; while (Mx.front() < l) Mx.pop_front(); while (Mn.front() < l) Mn.pop_front(); } ans += i - l + 1; } printf("%lld\n", ans); return 0; }  Code 2#include using namespace std; int n; long long k; vector v; struct Stack { vector v, mn = {LLONG_MAX}, mx = {LLONG_MIN}; void push(long long x) { v.push_back(x); mn.push_back(std::min(mn.back(), x)); mx.push_back(std::max(mx.back(), x)); } long long max() { return mx.back(); } long long min() { return mn.back(); } long long pop() { long long x = v.back(); v.pop_back(); mn.pop_back(); mx.pop_back(); return x; } bool empty() { return v.empty(); } } s1, s2; void remove() { if (s1.empty()) { while (!s2.empty()) s1.push(s2.pop()); } s1.pop(); } int main() { scanf("%d%lld", &n, &k); v.resize(n); for (auto &x : v) scanf("%lld", &x); long long ans = 0; int l = 0; for (int i = 0; i < n; ++i) { s2.push(v[i]); while (max(s1.max(), s2.max()) - min(s1.min(), s2.min()) > k) { remove(); l++; } ans += i - l + 1; } printf("%lld\n", ans); return 0; } Coprime Segment Code#include using namespace std; int n; vector v; struct Stack { vector stk, val = {0}; void push(long long x) { stk.push_back(x); val.push_back(__gcd(val.back(), x)); } long long top() { return val.back(); } long long pop() { long long x = stk.back(); stk.pop_back(); val.pop_back(); return x; } bool empty() { return stk.empty(); } } s1, s2; void remove() { if (s1.empty()) { while (!s2.empty()) s1.push(s2.pop()); } s1.pop(); } int main() { scanf("%d", &n); v.resize(n); for (auto &x : v) scanf("%lld", &x); int l = 0, ans = n + 1; for (int i = 0; i < n; ++i) { s2.push(v[i]); while (__gcd(s1.top(), s2.top()) == 1) { remove(); ans = min(ans, i - l + 1); l++; } } if (ans > n) ans = -1; printf("%d\n", ans); return 0; } step 3:Looped Playlist Code#include using namespace std; int n; long long p; vector v; int main() { scanf("%d%lld", &n, &p); v.resize(n); long long total = 0; for (auto &x : v) { scanf("%d", &x); total += x; } long long ans = (p - v[0]) / total * n + 1, sum = (p - v[0]) / total * total + v[0]; int l = 0, pos = 0; if (sum >= p) l = pos = 0; else { for (int i = n - 1; i >= 0; --i) { sum += v[i]; ++ans; if (sum >= p) { pos = l = i; break; } } } long long len = ans; for (int r = 1; r < n; ++r) { sum += v[r]; ++len; while (sum >= p) { sum -= v[l++]; l %= n; --len; } if (len + 1 < ans) { pos = (l - 1 + n) % n; ans = len + 1; } } printf("%d %lld\n", pos + 1, ans); return 0; } Total Length Code#include using namespace std; int n; long long s; vector v; int main() { scanf("%d%lld", &n, &s); v.resize(n); for (auto &x : v) scanf("%d", &x); int l = 0; long long ans = 0, sum = 0; for (int r = 0; r < n; ++r) { sum += v[r]; while (sum > s) sum -= v[l++]; ans += 1ll * (r - l + 2) * (r - l + 1) / 2; } printf("%lld\n", ans); return 0; } Che city Code#include using namespace std; int n, s; vector v; int main() { scanf("%d%d", &n, &s); v.resize(n + 1); for (int i = 1; i <= n; ++i) scanf("%d", &v[i]); int l = 1; long long ans = 1ll * n * (n + 1) / 2; for (int r = 1; r <= n; ++r) { while (v[r] - v[l] > s) ++l; ans -= r - l + 1; } printf("%lld\n", ans); return 0; } Stylish clothes Code#include using namespace std; vector> v; int a[4], b[4]; int main() { for (int i = 0, n; i < 4; ++i) { scanf("%d", &n); for (int j = 0, x; j < n; ++j) { scanf("%d", &x); v.push_back({x, i}); } } sort(v.begin(), v.end()); int l = 0, num = 0, ans = INT_MAX; int ll = 0, rr = 0; for (int r = 0; r < v.size(); ++r) { if (!b[v[r].second]++) ++num; if (num < 4) continue; while (b[v[l].second] > 1) { --b[v[l++].second]; } if (ans > v[r].first - v[l].first) { ans = v[r].first - v[l].first; ll = l, rr = r; } } a[v[ll].second] = v[ll].first; a[v[rr].second] = v[rr].first; for (int i = ll + 1; i < rr; ++i) { if (!a[v[i].second]) a[v[i].second] = v[i].first; } for (int i = 0; i < 4; ++i) printf("%d ", a[i]); return 0; }  Knapsack on a Segment Code#include using namespace std; int n, s; vector w, c; int main() { scanf("%d%d", &n, &s); w.resize(n); c.resize(n); for (auto &x : w) scanf("%d", &x); for (auto &x : c) scanf("%d", &x); int l = 0, sumw = 0; long long sumc = 0, ans = 0; for (int r = 0; r < n; ++r) { sumw += w[r]; sumc += c[r]; while (sumw > s) { sumw -= w[l]; sumc -= c[l++]; } ans = max(ans, sumc); } printf("%lld\n", ans); return 0; } Card Substrings Code#include using namespace std; const int MAXN = 1e5 + 5; int n, m; char s[MAXN], t[MAXN]; int Num[200], a[200]; int main() { scanf("%d%d%s%s", &n, &m, s, t); for (int i = 0; i < m; ++i) ++Num[t[i]]; int l = 0; long long ans = 0; for (int r = 0; r < n; ++r) { if (++a[s[r]] > Num[s[r]]) { while (s[l] != s[r]) { --a[s[l++]]; } --a[s[l++]]; } ans += r - l + 1; } printf("%lld\n", ans); return 0; } Not Very Rude Substring Code#include using namespace std; const int MAXN = 1e6 + 5; int n; long long c; char s[MAXN]; int main() { scanf("%d%lld%s", &n, &c, s); int l = 0, ans = 0, numa = 0, numb = 0; long long sum = 0; for (int r = 0; r < n; ++r) { if (s[r] == 'a') ++numa; else if (s[r] == 'b') { ++numb; sum += numa; } while (sum > c) { if (s[l] == 'a') { sum -= numb; --numa; } else if (s[l] == 'b') --numb; ++l; } ans = max(ans, r - l + 1); } printf("%d\n", ans); return 0; } A-B Knapsack Code#include using namespace std; int n, m, s, a, b; vector va, vb; int main() { scanf("%d%d%d%d%d", &n, &m, &s, &a, &b); va.resize(n); vb.resize(m); for (auto &x : va) scanf("%d", &x); for (auto &x : vb) scanf("%d", &x); sort(va.begin(), va.end(), greater()); sort(vb.begin(), vb.end(), greater()); int r = min(n, s / a) - 1, sum = (r + 1) * a; long long ans = 0; for (int i = 0; i <= r; ++i) ans += va[i]; long long cur = ans; for (int l = 0; l < min(m, s / b); ++l) { cur += vb[l]; sum += b; while (sum > s) { sum -= a; cur -= va[r--]; } ans = max(ans, cur); } printf("%lld\n", ans); return 0; } Segment with the Required Subset Code#include using namespace std; const int MAXM = 1005; int n, m; vector v; struct Stack{ vector v; vector> val; void init(int x) { bitset b = 0; b[x] = 1; val.push_back(b); } void push(int x, int t) { if (t) val.push_back(val.back() | val.back() << x); else val.push_back(val.back() | val.back() >> x); v.push_back(x); } int pop() { int x = v.back(); val.pop_back(); v.pop_back(); return x; } bitset top() { return val.back(); } bool empty() { return v.empty(); } } s1, s2; void remove() { if (s1.empty()) { while (!s2.empty()) s1.push(s2.pop(), 1); } s1.pop(); } int main() { scanf("%d%d", &n, &m); v.resize(n); for (auto &x : v) scanf("%d", &x); int l = 0, ans = n + 1; s1.init(0); s2.init(m); for (int r = 0; r < n; ++r) { s2.push(v[r], 0); while ((s1.top() & s2.top()).any()) { remove(); ans = min(ans, r - l + 1); l++; } } if (ans > n) ans = -1; printf("%d\n", ans); return 0; } all you need to two pointer