Day 13 – 4Sum, Subarray Sum = 0, XOR = K, Repeating and Missing Numbers

Today’s focus was on classic variations of subarray sum problems (sum = 0, XOR = k), k-sum extension (4Sum), and optimized detection of missing/repeating elements.

---

LeetCode 18 – 4Sum

---

1. Brute Force – 4 Nested Loops + Set

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    set<vector<int>> s;
    int n = nums.size();
    for(int i=0;i<n;i++) {
        for(int j=i+1;j<n;j++) {
            for(int k=j+1;k<n;k++) {
                for(int l=k+1;l<n;l++) {
                    long long sum = 1LL*nums[i] + nums[j] + nums[k] + nums[l];
                    if(sum == target) {
                        vector<int> temp = {nums[i], nums[j], nums[k], nums[l]};
                        sort(temp.begin(), temp.end());
                        s.insert(temp);
                    }
                }
            }
        }
    }
    return vector<vector<int>>(s.begin(), s.end());
}
// TC: O(n⁴ log 4) ≈ O(n⁴)
// SC: O(no. of unique quadruplets)

---

2. Better – 3 Loops + Hash Set (still inefficient)

Similar to 3Sum + hashmap, but still high complexity.

• TC: O(n³)

• SC: O(n)

---

3. Optimal – Two Pointer After Sorting

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    int n = nums.size();

    for (int i = 0; i < n; i++) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        for (int j = i+1; j < n; j++) {
            if (j > i+1 && nums[j] == nums[j-1]) continue;

            int left = j+1, right = n-1;
            while (left < right) {
                long long sum = 1LL*nums[i] + nums[j] + nums[left] + nums[right];
                if (sum < target) left++;
                else if (sum > target) right--;
                else {
                    res.push_back({nums[i], nums[j], nums[left], nums[right]});
                    while (left < right && nums[left] == nums[left+1]) left++;
                    while (left < right && nums[right] == nums[right-1]) right--;
                    left++; right--;
                }
            }
        }
    }
    return res;
}
// TC: O(n³)
// SC: O(1) excluding result

---

Longest Subarray with Sum = 0

int maxLen(vector<int>& A, int N) {
    unordered_map<int, int> mp;
    int sum = 0, maxLen = 0;

    for (int i = 0; i < N; i++) {
        sum += A[i];
        if (sum == 0) maxLen = i + 1;
        else if (mp.count(sum)) maxLen = max(maxLen, i - mp[sum]);
        else mp[sum] = i;
    }
    return maxLen;
}
// TC: O(n)
// SC: O(n)

---

Count Subarrays with XOR = K

int countSubarraysWithXorK(vector<int>& nums, int k) {
    unordered_map<int, int> mp;
    int count = 0, xr = 0;
    mp[0] = 1;

    for (int i = 0; i < nums.size(); i++) {
        xr ^= nums[i];
        int x = xr ^ k;
        if (mp.count(x)) count += mp[x];
        mp[xr]++;
    }
    return count;
}
// TC: O(n)
// SC: O(n)

---

Repeating and Missing Number in Array

Array from 1 to n where one number is missing and one is repeating

---

1. Brute Force – Count Each Element

pair<int,int> find(vector<int> &arr, int n){
    for(int i=1;i<=n;i++){
        int cnt=0;
        for(int j=0;j<n;j++)
            if(arr[j]==i) cnt++;
        if(cnt==2) rep=i;
        if(cnt==0) miss=i;
    }
    return {rep, miss};
}
// TC: O(n²)
// SC: O(1)

---

2. Better – Hash Frequency Array

pair<int,int> find(vector<int> &arr, int n){
    vector<int> freq(n+1, 0);
    for(int num : arr) freq[num]++;
    int rep = -1, miss = -1;
    for(int i = 1; i <= n; i++){
        if(freq[i] == 2) rep = i;
        if(freq[i] == 0) miss = i;
    }
    return {rep, miss};
}
// TC: O(n)
// SC: O(n)

---

3. Optimal – Using Math (Sum and Square Sum)

pair<int,int> find(vector<int> &arr, int n){
    long long s = 0, s2 = 0;
    long long sn = (n * (n + 1)) / 2;
    long long s2n = (n * (n + 1) * (2 * n + 1)) / 6;
    for(int i = 0; i < n; i++){
        s += arr[i];
        s2 += 1LL * arr[i] * arr[i];
    }
    long long val1 = s - sn;         // x - y
    long long val2 = s2 - s2n;       // x² - y² = (x - y)(x + y)
    val2 = val2 / val1;              // x + y
    int x = (val1 + val2) / 2;
    int y = x - val1;
    return {x, y}; // {repeating, missing}
}
// TC: O(n)
// SC: O(1)

---

4. Optimal – Using XOR

pair<int, int> find(vector<int> &arr, int n) {
    int xor1 = 0;
    for (int i = 0; i < n; i++) xor1 ^= arr[i];
    for (int i = 1; i <= n; i++) xor1 ^= i;

    int bit = xor1 & ~(xor1 - 1); // rightmost set bit

    int x = 0, y = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] & bit) x ^= arr[i];
        else y ^= arr[i];
    }
    for (int i = 1; i <= n; i++) {
        if (i & bit) x ^= i;
        else y ^= i;
    }

    // check which is repeating
    int cnt = 0;
    for (int i = 0; i < n; i++) if (arr[i] == x) cnt++;
    if (cnt == 2) return {x, y};
    return {y, x};
}
// TC: O(n)
// SC: O(1)

---