/
NumberOfSubsequencesThatSatisyTheGivenSumCondition.java
57 lines (46 loc) · 1.42 KB
/
NumberOfSubsequencesThatSatisyTheGivenSumCondition.java
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
// https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition
// Number of subsequences possible of an array of length is 2^(length - 1)
class Solution {
public int numSubseq(int[] nums, int target) {
long count = 0;
Arrays.sort(nums);
int[] map = new int[nums[nums.length - 1] + 1];
Arrays.fill(map, -1);
for (int i = 0; i < nums.length; i++) {
map[nums[i]] = i;
}
int last = -1;
for (int i = 0; i < map.length; i++) {
if (map[i] == -1) {
map[i] = last;
} else {
last = -i;
}
}
for (int i = 0; i < nums.length; i++) {
int upper = target - nums[i];
if (upper < nums[i]) continue;
int ix = upper >= map.length ? map[map.length - 1] : map[upper];
if (ix < 0) {
int lastAvailable = -ix;
ix = map[lastAvailable];
}
count += modPow(2, ix - i);
count %= 1000000007;
}
return (int) count;
}
long modPow(long base, int exp) {
long res = 1;
long mod = 1000000007;
base %= mod;
while (exp > 0) {
if (exp % 2 == 1) {
res = (res * base) % mod;
}
exp >>= 1;
base = (base * base) % mod;
}
return res;
}
}