Practice Questions — Competitive Programming Patterns in C++

int n = 16;
cout << ((n & (n - 1)) == 0);

int arr[] = {3, 1, 3, 1, 5};
int result = 0;
for (int x : arr) result ^= x;
cout << result;

int n = 13;  // 1101 in binary
cout << __builtin_popcount(n);

vector<int> v = {1, 2, 3, 4, 5};
int prefix[6] = {0};
for (int i = 0; i < 5; i++)
    prefix[i + 1] = prefix[i] + v[i];
cout << prefix[4] - prefix[1];

int n = 10;  // 1010
int result = n | (1 << 0);  // Set bit 0
cout << result;

vector<int> v = {1, 3, 5, 7, 9};
int target = 8;
int lo = 0, hi = v.size() - 1;
while (lo < hi) {
    int sum = v[lo] + v[hi];
    if (sum == target) {
        cout << v[lo] << " " << v[hi];
        break;
    } else if (sum < target) lo++;
    else hi--;
}
if (lo >= hi) cout << "Not found";

vector<int> arr = {2, 3, 5, 1, 4};
int k = 3;
int sum = 0;
for (int i = 0; i < k; i++) sum += arr[i];
int maxSum = sum;
for (int i = k; i < (int)arr.size(); i++) {
    sum += arr[i] - arr[i - k];
    maxSum = max(maxSum, sum);
}
cout << maxSum;

int n = 42;  // 101010
for (int i = 5; i >= 0; i--)
    cout << ((n >> i) & 1);

int n = 7;  // 0111
int cleared = n & ~(1 << 1);  // Clear bit 1
cout << cleared;

int a = 5, b = 3;
a = a ^ b;
b = a ^ b;
a = a ^ b;
cout << a << " " << b;

vector<int> nums = {1, 2, 3};
int n = nums.size();
for (int mask = 0; mask < (1 << n); mask++) {
    cout << "{ ";
    for (int i = 0; i < n; i++)
        if (mask & (1 << i))
            cout << nums[i] << " ";
    cout << "} ";
}

vector<int> v = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int maxSum = v[0], currSum = v[0];
for (int i = 1; i < (int)v.size(); i++) {
    currSum = max(v[i], currSum + v[i]);
    maxSum = max(maxSum, currSum);
}
cout << maxSum;

vector<int> nums = {1, 1, 1};
int k = 2;
unordered_map<int, int> prefixCount;
prefixCount[0] = 1;
int sum = 0, count = 0;
for (int x : nums) {
    sum += x;
    if (prefixCount.count(sum - k))
        count += prefixCount[sum - k];
    prefixCount[sum]++;
}
cout << count;

int n = 0;
for (int i = 0; i < 10; i++)
    if (i & 1) n++;
cout << n;

vector<int> v = {10, 20, 30, 40, 50};
int sum = 0;
for (int i = 1; i < (int)v.size(); i++)
    sum += v[i] - v[i - 1];
cout << sum;

int n = 255;  // 11111111
int count = 0;
while (n) {
    count++;
    n = n & (n - 1);
}
cout << count;

vector<int> v = {3, 1, -2, 5, -3, 2};
vector<int> prefix(v.size() + 1, 0);
for (int i = 0; i < (int)v.size(); i++)
    prefix[i + 1] = prefix[i] + v[i];
cout << prefix[4] - prefix[1];

vector<int> v = {1, 3, 5, 7, 9, 11};
int lo = 0, hi = v.size() - 1;
int target = 6;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (v[mid] <= target) lo = mid + 1;
    else hi = mid - 1;
}
cout << hi << " " << lo;

int x = 5;  // 101
int y = 3;  // 011
cout << (x & y) << " " << (x | y);

string s = "abcba";
int lo = 0, hi = s.size() - 1;
bool isPalin = true;
while (lo < hi) {
    if (s[lo] != s[hi]) { isPalin = false; break; }
    lo++; hi--;
}
cout << isPalin;

int x = 6;  // 110
int y = 3;  // 011
cout << (x ^ y);

int x = 12;
cout << (x >> 2);

cout << (1 << 10);

vector<int> v = {1, 2, 3, 4, 5, 6};
int lo = 0, hi = v.size() - 1;
int target = 7;
int pairs = 0;
while (lo < hi) {
    int sum = v[lo] + v[hi];
    if (sum == target) { pairs++; lo++; hi--; }
    else if (sum < target) lo++;
    else hi--;
}
cout << pairs;

vector<int> v = {10, 20, 30, 40, 50};
vector<int> prefix(6, 0);
for (int i = 0; i < 5; i++)
    prefix[i + 1] = prefix[i] + v[i];
// Sum of v[1..3]
cout << prefix[4] - prefix[1];

int n = 20;  // 10100
int toggled = n ^ (1 << 2);  // Toggle bit 2
cout << toggled;

vector<int> arr = {4, 2, 1, 5, 3};
int k = 2;
int n = arr.size();
int windowMin = INT_MAX;
for (int i = 0; i <= n - k; i++) {
    int localMax = *max_element(arr.begin() + i, arr.begin() + i + k);
    windowMin = min(windowMin, localMax);
}
cout << windowMin;

int n = 15;  // 1111
int lowest = n & (-n);
cout << lowest;

int n = 12;  // 1100
int lowest = n & (-n);
cout << lowest;

// Greedy: minimum coins for amount
vector<int> coins = {1, 5, 10, 25};
int amount = 41;
int count = 0;
for (int i = coins.size() - 1; i >= 0; i--) {
    count += amount / coins[i];
    amount %= coins[i];
}
cout << count;

int n = 8;  // 1000
cout << (n & (n - 1));

vector<int> v = {2, 4, 6, 8, 10};
int lo = 0, hi = v.size() - 1;
int target = 14;
bool found = false;
while (lo < hi) {
    int sum = v[lo] + v[hi];
    if (sum == target) { found = true; break; }
    else if (sum < target) lo++;
    else hi--;
}
cout << found << " " << lo << " " << hi;

vector<int> arr = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
vector<int> result;
for (int i = 0; i <= (int)arr.size() - k; i++) {
    int mx = *max_element(arr.begin() + i, arr.begin() + i + k);
    result.push_back(mx);
}
for (int x : result) cout << x << " ";

int a = 10, b = 7;
cout << (a & b) << " " << (a | b) << " " << (a ^ b);