maps_prefix_array.cpp

#include<bits/stdc++.h>
using namespace std;
int main()
{
    // 1. > maps in sorted order (revise)
    // 2. > unordered maps (hashing)
    // 3. > when to use maps and when to use unordered maps


    // 4. > concept of prefix array(v.v.v.imp)
    // 5. > check whether the array has subarray with 0 sum
    // 6. > max length of the subarray with 0 sum
    // 7. > count of subarrays with 0 sum
    // 8. > check whether the array has subarray with sum k
    // 9. > max length of the subarray with sum k
    // 10. > count of subarrays with sum k


    // map<int, int> m;
    // m[2]++; m[3]++;
    // for (auto i : m)
    // {
    //  cout << i.first << " " << i.second << endl;
    // }

    // m[1]++;
    // for (auto i : m)
    // {
    //  cout << i.first << " " << i.second << endl;
    // }

    // unordered_map<int, int> um;


    // um[3]++; um[2]++;
    // for (auto i : um)
    // {
    //  cout << i.first << " " << i.second << endl;
    // }

    // um[1]++;
    // for (auto i : um)
    // {
    //  cout << i.first << " " << i.second << endl;
    // }
//internally implemented in the form of hash table
//no order of keys



    //prefix array
    // int n; cin >> n;
    // vector<int> v(n + 1);
    // for (int i = 1; i <= n; i++) cin >> v[i];
    // int q; cin >> q;
    // while (q--)
    // {
    //  int l, r; cin >> l >> r;
    //  int sum = 0;
    //  for (int i = l; i <= r; i++) sum += v[i];
    //  cout << sum << endl;
    // }

    //worst case complexity=>O(N*N)
    //1s allowed limit=>10^8


    int n; cin >> n;
    vector<int> v(n + 1);//1 indexing
    for (int i = 1; i <= n; i++) cin >> v[i];
    v[0] = 0;
    // vector<int> prefix(n + 1, 0);
    // for (int i = 1; i <= n; i++)
    // {
    //  prefix[i] += prefix[i - 1] + v[i];//formula for prefix array
    // }

    // // for (int i = 1; i <= n; i++) cout << v[i] << " "; cout << endl;
    // // for (int i = 1; i <= n; i++) cout << prefix[i] << " "; cout << endl;


    // //use of prefx array
    // int q; cin >> q;
    // while (q--)
    // {
    //  int l, r; cin >> l >> r;
    //  int sum = prefix[r] - prefix[l - 1]; //2nd formlua
    //  // O(1)
    //  cout << sum << endl;
    // }

    // O(N)->optimisation using prefix array

//check whether the array has subarray with 0 sum

    map<int, int> m;
    int tempsum = 0; bool flag = false;
    for (int i = 1; i <= n; i++)
    {
        tempsum += v[i];
        if ((tempsum == 0) || (m.find(tempsum) != m.end()))
        {
            //either sum is zero or it is already present
            flag = true; break;
        }
        else
        {
            m[tempsum]++;
        }
    }
    if (flag) cout << "FOUND" << endl;
    else cout << "NOT FOUND" << endl;

    // T.C->O(n*logn)
    // S.C->O(n)
    return 0;
}