CodingProblems/ConsecutiveNumberSum.java at master · PerrySong/CodingProblems · GitHub

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
importjava.util.HashSet;
importjava.util.Set;

publicclassConsecutiveNumberSum {

/**
 Given a positive integer N, how many ways can we write it as a sum of consecutive positive integers?

 Example 1:

 Input: 5
 Output: 2
 Explanation: 5 = 5 = 2 + 3
 Example 2:

 Input: 9
 Output: 3
 Explanation: 9 = 9 = 4 + 5 = 2 + 3 + 4
 Example 3:

 Input: 15
 Output: 4
 Explanation: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5
 Note: 1 <= N <= 10 ^ 9.
 */

// Memory limit eceed
publicstaticintconsecutiveNumbersSum(intN) {
if (N <= 0) return0;
intres = 0;
long[] sums = newlong[N + 1];
Set<Long> sumSet = newHashSet<>();
sumSet.add((long)0);
for (inti = 1; i < sums.length; i++) {
sums[i] = sums[i - 1] + i;
sumSet.add(sums[i]);
 }

for (inti = 0; i < sums.length; i++) {
if (sumSet.contains(sums[i] - N))
res++;
 }
returnres;
 }


publicstaticvoidmain(String[] args) {
System.out.println(consecutiveNumbersSum(855204));
 }
}