Repository navigation
Expand file tree
/
Copy pathDifference.java
More file actions
119 lines (91 loc) · 1.9 KB
/
Copy pathDifference.java
File metadata and controls
119 lines (91 loc) · 1.9 KB
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;
public class Difference {
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int size = in.nextInt();
int k = in.nextInt();
int input[] = new int[size];
for(int i = 0; i < size; i++)
{
int value = in.nextInt();
input[i] = value;
}
diff(input, k);
}
private static void diff(int[] in, int k) {
// sort
in = sort(in);
int[] dif = new int[in.length];
dif[0] = 0;
for(int i = 1; i < in.length; i++)
dif[i] = in[i] - in[i-1];
int sum = 0;
int amount = 0;
//System.out.println(Arrays.toString(dif));
for(int i = 0; i < in.length; i++)
{
sum = 0;
for(int j = i + 1; j < in.length; j++)
{
sum += dif[j];
if(sum == k)
amount++;
else if(sum > k)
break;
}
}
System.out.println(amount);
}
public static int[] sort(int[] a)
{
if(a.length == 1)
return a;
int[] l = new int[(a.length/2)];
int[] r = new int[(int) Math.ceil(((double)a.length)/2)];
for(int i = 0; i < a.length/2; i++)
l[i] = a[i];
for(int i = a.length/2; i < a.length; i++)
r[i - a.length/2] = a[i];
l = sort(l);
r = sort(r);
return merge(l,r);
}
public static int[] merge(int[] a, int[] b)
{
int[] c = new int[a.length + b.length];
int aIndex = 0;
int bIndex = 0;
int cIndex = 0;
while((aIndex < a.length) && (bIndex < b.length))
{
if(a[aIndex] < b[bIndex])
{
c[cIndex] = a[aIndex];
aIndex++;
cIndex++;
}
else
{
c[cIndex] = b[bIndex];
bIndex++;
cIndex++;
}
}
while(bIndex < b.length)
{
c[cIndex] = b[bIndex];
bIndex++;
cIndex++;
}
while(aIndex < a.length)
{
c[cIndex] = a[aIndex];
aIndex++;
cIndex++;
}
return c;
}
}