-
Notifications
You must be signed in to change notification settings - Fork 0
/
1-Willy1.cpp
74 lines (56 loc) · 1.55 KB
/
1-Willy1.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
//BIAR MANTAB LAH YA
#define Willy using
#define Indrayana namespace
#define Komara std
Willy Indrayana Komara;
using namespace std::chrono;
bool besarDulu(const int &a, const int &b)
{
return a > b;
}
using ll = long long int;
int findSubarraySum(int arr[], int n, int sum)
{
// STL map to store number of subarrays
// starting from index zero having
// particular value of sum.
unordered_map<int, int> prevSum;
int res = 0;
// Sum of elements so far.
int currsum = 0;
for (int i = 0; i < n; i++) {
// Add current element to sum so far.
currsum &= arr[i];
// If currsum is equal to desired sum,
// then a new subarray is found. So
// increase count of subarrays.
if (currsum == sum)
res++;
// currsum exceeds given sum by currsum
// - sum. Find number of subarrays having
// this sum and exclude those subarrays
// from currsum by increasing count by
// same amount.
if (prevSum.find(currsum - sum) !=
prevSum.end())
res += (prevSum[currsum - sum]);
// Add currsum value to count of
// different values of sum.
prevSum[currsum]++;
}
return res;
}
int main()
{
int arr[] = { 10, 2, -2, -20, 10 };
int sum = -10;
int n = sizeof(arr) / sizeof(arr[0]);
cout << findSubarraySum(arr, n, sum);
return 0;
}
/*
0001
0111
0001
*/