#include <bits/stdc++.h>
using namespace std;

vector<string> results;
long long cnt = 0;

void backtrack(long long i, long long sum, long long m, string& signs, long long k) {
    // Nếu đã đủ k cách -> dừng
    if (cnt >= k) return;

    // Tính tổng các số còn lại: 1 + 2 + ... + i
    long long remaining = i * (i + 1) / 2;

    // Cắt nhánh nếu không thể đạt m
    if (abs(m - sum) > remaining) return;

    // Nếu đã xét hết
    if (i == 0) {
        if (sum == m) {
            results.push_back(signs);
            cnt++;
        }
        return;
    }

    // Thử dấu '+'
    signs[i-1] = '+';
    backtrack(i-1, sum + i, m, signs, k);

    // Thử dấu '-'
    signs[i-1] = '-';
    backtrack(i-1, sum - i, m, signs, k);
}

┌─────────────────────────────────┐
│   Bắt đầu duyệt                 │
│   sum = 0, i = n                │
└───────────────┬─────────────────┘
                │
        ┌───────▼────────┐
        │ Tính cận:      │
        │ remaining =    │
        │ i*(i+1)/2      │
        └───────┬────────┘
                │
        ┌───────▼────────┐
        │ |m-sum| >      │
        │ remaining ?    │
        └───────┬────────┘
    Có ┌────────┴─┐ Không
       ▼          ▼
       │       i == 0 ?
       │          │
       │      Có ┌┴────┐ Không
       │         │     └──────────┐
       │     sum==m?              │
       │        │                 │
       │ Không ┌┴────┐ Có         │
       │       |     ▼            ▼
       │┌──────┘ Lưu kết quả  Thử dấu +/-
       ▼▼                         │
    Cắt nhánh                     │
       │                          ▼
       └────────────────────► Tiếp tục

#include <iostream>
#include <vector>
using namespace std;

pair<int, int> twoSumSorted(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;

    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) {
            return {left, right}; // Trả về chỉ số
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }

    return {-1, -1}; // Không tìm thấy
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11};
    int target = 12;

    pair<int, int> result = twoSumSorted(arr, target);

    if (result.first != -1) {
        cout << "Found: " << arr[result.first] << " + " << arr[result.second] 
             << " = " << target << endl;
    } else {
        cout << "Not found" << endl;
    }

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int removeDuplicates(vector<int>& arr) {
    if (arr.empty()) return 0;

    int j = 0; // Con trỏ lưu vị trí cuối cùng của phần tử không trùng
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] != arr[j]) {
            j++;
            arr[j] = arr[i];
        }
    }

    return j + 1; // Số lượng phần tử không trùng
}

int main() {
    vector<int> arr = {1, 1, 2, 2, 2, 3, 4, 4, 5};

    int newLength = removeDuplicates(arr);

    cout << "Mang sau khi loai trung: ";
    for (int i = 0; i < newLength; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int longestSubarraySumLE(vector<int>& arr, int target) {
    int left = 0, sum = 0, maxLength = 0;

    for (int right = 0; right < arr.size(); right++) {
        sum += arr[right];

        // Nếu tổng vượt quá target, dịch left sang phải
        while (sum > target && left <= right) {
            sum -= arr[left];
            left++;
        }

        // Cập nhật độ dài cửa sổ
        maxLength = max(maxLength, right - left + 1);
    }

    return maxLength;
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};
    int target = 10;

    cout << "Do dai day con dai nhat co tong <= " << target << ": "
         << longestSubarraySumLE(arr, target) << endl;

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1; // Không tìm thấy
}

#include <iostream>
#include <vector>
using namespace std;

int firstOccurrence(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    int result = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] >= target) {
            result = mid;
            right = mid - 1; // Tiếp tục tìm bên trái
        } else {
            left = mid + 1;
        }
    }

    return result; // Trả về chỉ số đầu tiên có giá trị >= target
}

#include <iostream>
#include <vector>
using namespace std;

int lastOccurrence(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    int result = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] <= target) {
            result = mid;
            left = mid + 1; // Tiếp tục tìm bên phải
        } else {
            right = mid - 1;
        }
    }

    return result; // Trả về chỉ số cuối cùng có giá trị <= target
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> threeSumZero(vector<int>& arr) {
    vector<vector<int>> result;
    int n = arr.size();

    sort(arr.begin(), arr.end()); // Đảm bảo mảng đã sắp xếp

    for (int i = 0; i < n - 2; i++) {
        // Bỏ qua các giá trị trùng nhau
        if (i > 0 && arr[i] == arr[i-1]) continue;

        int left = i + 1, right = n - 1;
        while (left < right) {
            int sum = arr[i] + arr[left] + arr[right];
            if (sum == 0) {
                result.push_back({arr[i], arr[left], arr[right]});

                // Bỏ qua các giá trị trùng
                while (left < right && arr[left] == arr[left+1]) left++;
                while (left < right && arr[right] == arr[right-1]) right--;

                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }

    return result;
}

#include <iostream>
#include <vector>
#include <climits>
#include <cmath>
using namespace std;

pair<int, int> closestSum(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    int minDiff = INT_MAX;
    pair<int, int> result;

    while (left < right) {
        int sum = arr[left] + arr[right];
        int diff = abs(sum - target);

        if (diff < minDiff) {
            minDiff = diff;
            result = {arr[left], arr[right]};
        }

        if (sum < target) {
            left++;
        } else {
            right--;
        }
    }

    return result;
}