CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Google Interview Question for Software Engineer / Developers


Country: India
Interview Type: Written Test



Comment hidden because of low score. Click to expand.
13
of 13 vote

Maximum sum can be = N*(N+1) / 2 for any subset considered.
Hence put S = (N*(N+1) / 2) in subset sum problem.

i.e dp[i][j] = dp[i-1][j] + dp[i-1][j-a[i]]; // check for cases when j-a[i] < 0.
iterate i from 1 to N and j from 0 to S.
ans = 0;
again iterate from j = 0 to S and check if j is prime, and if j is prime then
ans = ans + dp[N][j];

output ans.

- Anonymous December 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why the "Maximum sum can be = N*(N+1) / 2 "?

- Anonymous December 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please provide an explanation for your method?

- Srikant Aggarwal December 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It means that let's
dp[i][j] is the number of ways to collect the sum j from i first numbers.
then if we are looking for i + 1 number, let's look from j to 0 to every sum we can collect. (the direction is important if you will skip the i-th param). dp[i+1][j+a[i+1]] += dp[i][j]. And then for each prime number we will look at the dp table. But don't forget that we can don't use the i+1 number, so we also should make dp[i+1][j] += dp[i][j]

- Alex Fetisov December 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

just checked with code, if N=100, then max sum is 5050 and there always exists some subset of numbers between 1 and hundred with which you can build all the sums between 1 and max ie 5050

- kc January 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

1 
K:1
2 
K:2
2 1 
K:3
3 1 
K:4
3 2 
K:5
3 2 1 
K:6
4 2 1 
K:7
4 3 1 
K:8
4 3 2 
K:9
4 3 2 1 
K:10
5 3 2 1 
K:11
5 4 2 1 
K:12
5 4 3 1 
K:13
5 4 3 2 
K:14
5 4 3 2 1 
K:15
6 4 3 2 1 
K:16
6 5 3 2 1 
K:17
6 5 4 2 1 
K:18
6 5 4 3 1 
K:19
6 5 4 3 2 
K:20
6 5 4 3 2 1 
K:21
7 5 4 3 2 1 
K:22
7 6 4 3 2 1 
K:23
7 6 5 3 2 1 
K:24
7 6 5 4 2 1 
K:25
7 6 5 4 3 1 
K:26
7 6 5 4 3 2 
K:27
7 6 5 4 3 2 1 
K:28
8 6 5 4 3 2 1 
K:29
8 7 5 4 3 2 1 
K:30
8 7 6 4 3 2 1 
K:31
8 7 6 5 3 2 1 
K:32
8 7 6 5 4 2 1 
K:33
8 7 6 5 4 3 1 
K:34
8 7 6 5 4 3 2 
K:35
8 7 6 5 4 3 2 1 
K:36
9 7 6 5 4 3 2 1 
K:37
9 8 6 5 4 3 2 1 
K:38
9 8 7 5 4 3 2 1 
K:39
9 8 7 6 4 3 2 1 
K:40
9 8 7 6 5 3 2 1 
K:41
9 8 7 6 5 4 2 1 
K:42
9 8 7 6 5 4 3 1 
K:43
9 8 7 6 5 4 3 2 
K:44
9 8 7 6 5 4 3 2 1 
K:45
10 8 7 6 5 4 3 2 1 
K:46
10 9 7 6 5 4 3 2 1 
K:47
10 9 8 6 5 4 3 2 1 
K:48
10 9 8 7 5 4 3 2 1 
K:49
10 9 8 7 6 4 3 2 1 
K:50
10 9 8 7 6 5 3 2 1 
K:51
10 9 8 7 6 5 4 2 1 
K:52
10 9 8 7 6 5 4 3 1 
K:53
10 9 8 7 6 5 4 3 2 
K:54
10 9 8 7 6 5 4 3 2 1 
K:55
11 9 8 7 6 5 4 3 2 1 
K:56
11 10 8 7 6 5 4 3 2 1 
K:57
11 10 9 7 6 5 4 3 2 1 
K:58
11 10 9 8 6 5 4 3 2 1 
K:59
11 10 9 8 7 5 4 3 2 1 
K:60
11 10 9 8 7 6 4 3 2 1 
K:61
11 10 9 8 7 6 5 3 2 1 
K:62
11 10 9 8 7 6 5 4 2 1 
K:63
11 10 9 8 7 6 5 4 3 1 
K:64
11 10 9 8 7 6 5 4 3 2 
K:65
11 10 9 8 7 6 5 4 3 2 1 
K:66
12 10 9 8 7 6 5 4 3 2 1 
K:67
12 11 9 8 7 6 5 4 3 2 1 
K:68
12 11 10 8 7 6 5 4 3 2 1 
K:69
12 11 10 9 7 6 5 4 3 2 1 
K:70
12 11 10 9 8 6 5 4 3 2 1 
K:71
12 11 10 9 8 7 5 4 3 2 1 
K:72
12 11 10 9 8 7 6 4 3 2 1 
K:73
12 11 10 9 8 7 6 5 3 2 1 
K:74
12 11 10 9 8 7 6 5 4 2 1 
K:75
12 11 10 9 8 7 6 5 4 3 1 
K:76
12 11 10 9 8 7 6 5 4 3 2 
K:77
12 11 10 9 8 7 6 5 4 3 2 1 
K:78
13 11 10 9 8 7 6 5 4 3 2 1 
K:79
13 12 10 9 8 7 6 5 4 3 2 1 
K:80
13 12 11 9 8 7 6 5 4 3 2 1 
K:81
13 12 11 10 8 7 6 5 4 3 2 1 
K:82
13 12 11 10 9 7 6 5 4 3 2 1 
K:83
13 12 11 10 9 8 6 5 4 3 2 1 
K:84
13 12 11 10 9 8 7 5 4 3 2 1 
K:85
13 12 11 10 9 8 7 6 4 3 2 1 
K:86
13 12 11 10 9 8 7 6 5 3 2 1 
K:87
13 12 11 10 9 8 7 6 5 4 2 1 
K:88
13 12 11 10 9 8 7 6 5 4 3 1 
K:89
13 12 11 10 9 8 7 6 5 4 3 2 
K:90
13 12 11 10 9 8 7 6 5 4 3 2 1 
K:91
14 12 11 10 9 8 7 6 5 4 3 2 1 
K:92
14 13 11 10 9 8 7 6 5 4 3 2 1 
K:93
14 13 12 10 9 8 7 6 5 4 3 2 1 
K:94
14 13 12 11 9 8 7 6 5 4 3 2 1 
K:95
14 13 12 11 10 8 7 6 5 4 3 2 1 
K:96
14 13 12 11 10 9 7 6 5 4 3 2 1 
K:97
14 13 12 11 10 9 8 6 5 4 3 2 1 
K:98
14 13 12 11 10 9 8 7 5 4 3 2 1 
K:99
14 13 12 11 10 9 8 7 6 4 3 2 1 
K:100
14 13 12 11 10 9 8 7 6 5 3 2 1 
K:101
14 13 12 11 10 9 8 7 6 5 4 2 1 
K:102
14 13 12 11 10 9 8 7 6 5 4 3 1 
K:103
14 13 12 11 10 9 8 7 6 5 4 3 2 
K:104
14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:105
15 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:106
15 14 12 11 10 9 8 7 6 5 4 3 2 1 
K:107
15 14 13 11 10 9 8 7 6 5 4 3 2 1 
K:108
15 14 13 12 10 9 8 7 6 5 4 3 2 1 
K:109
15 14 13 12 11 9 8 7 6 5 4 3 2 1 
K:110
15 14 13 12 11 10 8 7 6 5 4 3 2 1 
K:111
15 14 13 12 11 10 9 7 6 5 4 3 2 1 
K:112
15 14 13 12 11 10 9 8 6 5 4 3 2 1 
K:113
15 14 13 12 11 10 9 8 7 5 4 3 2 1 
K:114
15 14 13 12 11 10 9 8 7 6 4 3 2 1 
K:115
15 14 13 12 11 10 9 8 7 6 5 3 2 1 
K:116
15 14 13 12 11 10 9 8 7 6 5 4 2 1 
K:117
15 14 13 12 11 10 9 8 7 6 5 4 3 1 
K:118
15 14 13 12 11 10 9 8 7 6 5 4 3 2 
K:119
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:120
16 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:121
16 15 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:122
16 15 14 12 11 10 9 8 7 6 5 4 3 2 1 
K:123
16 15 14 13 11 10 9 8 7 6 5 4 3 2 1 
K:124
16 15 14 13 12 10 9 8 7 6 5 4 3 2 1 
K:125
16 15 14 13 12 11 9 8 7 6 5 4 3 2 1 
K:126
16 15 14 13 12 11 10 8 7 6 5 4 3 2 1 
K:127
16 15 14 13 12 11 10 9 7 6 5 4 3 2 1 
K:128
16 15 14 13 12 11 10 9 8 6 5 4 3 2 1 
K:129
16 15 14 13 12 11 10 9 8 7 5 4 3 2 1 
K:130
16 15 14 13 12 11 10 9 8 7 6 4 3 2 1 
K:131
16 15 14 13 12 11 10 9 8 7 6 5 3 2 1 
K:132
16 15 14 13 12 11 10 9 8 7 6 5 4 2 1 
K:133
16 15 14 13 12 11 10 9 8 7 6 5 4 3 1 
K:134
16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 
K:135
16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:136
17 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:137
17 16 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:138
17 16 15 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:139
17 16 15 14 12 11 10 9 8 7 6 5 4 3 2 1 
K:140
17 16 15 14 13 11 10 9 8 7 6 5 4 3 2 1 
K:141
17 16 15 14 13 12 10 9 8 7 6 5 4 3 2 1 
K:142
17 16 15 14 13 12 11 9 8 7 6 5 4 3 2 1 
K:143
17 16 15 14 13 12 11 10 8 7 6 5 4 3 2 1 
K:144
17 16 15 14 13 12 11 10 9 7 6 5 4 3 2 1 
K:145
17 16 15 14 13 12 11 10 9 8 6 5 4 3 2 1 
K:146
17 16 15 14 13 12 11 10 9 8 7 5 4 3 2 1 
K:147
17 16 15 14 13 12 11 10 9 8 7 6 4 3 2 1 
K:148
17 16 15 14 13 12 11 10 9 8 7 6 5 3 2 1 
K:149
17 16 15 14 13 12 11 10 9 8 7 6 5 4 2 1 
K:150
17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 1 
K:151
17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 
K:152
17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:153
18 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:154
18 17 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:155
18 17 16 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:156
18 17 16 15 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:157
18 17 16 15 14 12 11 10 9 8 7 6 5 4 3 2 1 
K:158
18 17 16 15 14 13 11 10 9 8 7 6 5 4 3 2 1 
K:159
18 17 16 15 14 13 12 10 9 8 7 6 5 4 3 2 1 
K:160
18 17 16 15 14 13 12 11 9 8 7 6 5 4 3 2 1 
K:161
18 17 16 15 14 13 12 11 10 8 7 6 5 4 3 2 1 
K:162
18 17 16 15 14 13 12 11 10 9 7 6 5 4 3 2 1 
K:163
18 17 16 15 14 13 12 11 10 9 8 6 5 4 3 2 1 
K:164
18 17 16 15 14 13 12 11 10 9 8 7 5 4 3 2 1 
K:165
18 17 16 15 14 13 12 11 10 9 8 7 6 4 3 2 1 
K:166
18 17 16 15 14 13 12 11 10 9 8 7 6 5 3 2 1 
K:167
18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 2 1 
K:168
18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 1 
K:169
18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 
K:170
18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:171
19 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:172
19 18 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:173
19 18 17 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:174
19 18 17 16 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:175
19 18 17 16 15 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:176
19 18 17 16 15 14 12 11 10 9 8 7 6 5 4 3 2 1 
K:177
19 18 17 16 15 14 13 11 10 9 8 7 6 5 4 3 2 1 
K:178
19 18 17 16 15 14 13 12 10 9 8 7 6 5 4 3 2 1 
K:179
19 18 17 16 15 14 13 12 11 9 8 7 6 5 4 3 2 1 
K:180
19 18 17 16 15 14 13 12 11 10 8 7 6 5 4 3 2 1 
K:181
19 18 17 16 15 14 13 12 11 10 9 7 6 5 4 3 2 1 
K:182
19 18 17 16 15 14 13 12 11 10 9 8 6 5 4 3 2 1 
K:183
19 18 17 16 15 14 13 12 11 10 9 8 7 5 4 3 2 1 
K:184
19 18 17 16 15 14 13 12 11 10 9 8 7 6 4 3 2 1 
K:185
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 3 2 1 
K:186
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 2 1 
K:187
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 1 
K:188
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 
K:189
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:190
20 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:191
20 19 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:192
20 19 18 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:193
20 19 18 17 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:194
20 19 18 17 16 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:195
20 19 18 17 16 15 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:196
20 19 18 17 16 15 14 12 11 10 9 8 7 6 5 4 3 2 1 
K:197
20 19 18 17 16 15 14 13 11 10 9 8 7 6 5 4 3 2 1 
K:198
20 19 18 17 16 15 14 13 12 10 9 8 7 6 5 4 3 2 1 
K:199
20 19 18 17 16 15 14 13 12 11 9 8 7 6 5 4 3 2 1 
K:200
20 19 18 17 16 15 14 13 12 11 10 8 7 6 5 4 3 2 1 
K:201
20 19 18 17 16 15 14 13 12 11 10 9 7 6 5 4 3 2 1 
K:202
20 19 18 17 16 15 14 13 12 11 10 9 8 6 5 4 3 2 1 
K:203
20 19 18 17 16 15 14 13 12 11 10 9 8 7 5 4 3 2 1 
K:204
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 4 3 2 1 
K:205
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 3 2 1 
K:206
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 2 1 
K:207
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 1 
K:208
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 
K:209
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:210
21 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:211
21 20 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:212
21 20 19 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:213
21 20 19 18 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:214
21 20 19 18 17 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:215
21 20 19 18 17 16 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:216
21 20 19 18 17 16 15 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:217
21 20 19 18 17 16 15 14 12 11 10 9 8 7 6 5 4 3 2 1 
K:218
21 20 19 18 17 16 15 14 13 11 10 9 8 7 6 5 4 3 2 1 
K:219
21 20 19 18 17 16 15 14 13 12 10 9 8 7 6 5 4 3 2 1 
K:220
21 20 19 18 17 16 15 14 13 12 11 9 8 7 6 5 4 3 2 1 
K:221
21 20 19 18 17 16 15 14 13 12 11 10 8 7 6 5 4 3 2 1 
K:222
21 20 19 18 17 16 15 14 13 12 11 10 9 7 6 5 4 3 2 1 
K:223
21 20 19 18 17 16 15 14 13 12 11 10 9 8 6 5 4 3 2 1 
K:224
21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 5 4 3 2 1 
K:225
21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 4 3 2 1 
K:226
21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 3 2 1 
K:227
21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 2 1 
K:228
21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 1 
K:229
21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 
K:230
21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:231
22 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:232
22 21 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:233
22 21 20 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:234
22 21 20 19 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:235
22 21 20 19 18 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:236
22 21 20 19 18 17 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:237
22 21 20 19 18 17 16 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:238
22 21 20 19 18 17 16 15 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:239
22 21 20 19 18 17 16 15 14 12 11 10 9 8 7 6 5 4 3 2 1 
K:240
22 21 20 19 18 17 16 15 14 13 11 10 9 8 7 6 5 4 3 2 1 
K:241
22 21 20 19 18 17 16 15 14 13 12 10 9 8 7 6 5 4 3 2 1 
K:242
22 21 20 19 18 17 16 15 14 13 12 11 9 8 7 6 5 4 3 2 1 
K:243
22 21 20 19 18 17 16 15 14 13 12 11 10 8 7 6 5 4 3 2 1 
K:244
22 21 20 19 18 17 16 15 14 13 12 11 10 9 7 6 5 4 3 2 1 
K:245
22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 6 5 4 3 2 1 
K:246
22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 5 4 3 2 1 
K:247
22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 4 3 2 1 
K:248
22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 3 2 1 
K:249
22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 2 1 
K:250
22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 1 
K:251
22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 
K:252
22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:253
23 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:254
23 22 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:255
23 22 21 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:256
23 22 21 20 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:257
23 22 21 20 19 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:258
23 22 21 20 19 18 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:259
23 22 21 20 19 18 17 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:260
23 22 21 20 19 18 17 16 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:261
23 22 21 20 19 18 17 16 15 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:262
23 22 21 20 19 18 17 16 15 14 12 11 10 9 8 7 6 5 4 3 2 1 
K:263
23 22 21 20 19 18 17 16 15 14 13 11 10 9 8 7 6 5 4 3 2 1 
K:264
23 22 21 20 19 18 17 16 15 14 13 12 10 9 8 7 6 5 4 3 2 1 
K:265
23 22 21 20 19 18 17 16 15 14 13 12 11 9 8 7 6 5 4 3 2 1 
K:266
23 22 21 20 19 18 17 16 15 14 13 12 11 10 8 7 6 5 4 3 2 1 
K:267
23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 7 6 5 4 3 2 1 
K:268
23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 6 5 4 3 2 1 
K:269
23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 5 4 3 2 1 
K:270
23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 4 3 2 1 
K:271
23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 3 2 1 
K:272
23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 2 1 
K:273
23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 1 
K:274
23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 
K:275
23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:276
24 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:277
24 23 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:278
24 23 22 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:279
24 23 22 21 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:280
24 23 22 21 20 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:281
24 23 22 21 20 19 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:282
24 23 22 21 20 19 18 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:283
24 23 22 21 20 19 18 17 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:284
24 23 22 21 20 19 18 17 16 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:285
24 23 22 21 20 19 18 17 16 15 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:286
24 23 22 21 20 19 18 17 16 15 14 12 11 10 9 8 7 6 5 4 3 2 1 
K:287
24 23 22 21 20 19 18 17 16 15 14 13 11 10 9 8 7 6 5 4 3 2 1 
K:288
24 23 22 21 20 19 18 17 16 15 14 13 12 10 9 8 7 6 5 4 3 2 1 
K:289
24 23 22 21 20 19 18 17 16 15 14 13 12 11 9 8 7 6 5 4 3 2 1 
K:290
24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 8 7 6 5 4 3 2 1 
K:291
24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 7 6 5 4 3 2 1 
K:292
24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 6 5 4 3 2 1 
K:293
24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 5 4 3 2 1 
K:294
24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 4 3 2 1 
K:295
24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 3 2 1 
K:296
24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 2 1 
K:297
24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 1 
K:298
24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 
K:299
24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:300
25 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:301
25 24 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:302
25 24 23 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:303
25 24 23 22 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:304
25 24 23 22 21 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:305
25 24 23 22 21 20 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:306
25 24 23 22 21 20 19 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:307
25 24 23 22 21 20 19 18 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:308
25 24 23 22 21 20 19 18 17 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:309
25 24 23 22 21 20 19 18 17 16 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:310
25 24 23 22 21 20 19 18 17 16 15 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:311
25 24 23 22 21 20 19 18 17 16 15 14 12 11 10 9 8 7 6 5 4 3 2 1 
K:312
25 24 23 22 21 20 19 18 17 16 15 14 13 11 10 9 8 7 6 5 4 3 2 1 
K:313
25 24 23 22 21 20 19 18 17 16 15 14 13 12 10 9 8 7 6 5 4 3 2 1 
K:314
25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 9 8 7 6 5 4 3 2 1 
K:315
25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 8 7 6 5 4 3 2 1 
K:316
25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 7 6 5 4 3 2 1 
K:317
25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 6 5 4 3 2 1 
K:318
25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 5 4 3 2 1 
K:319
25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 4 3 2 1 
K:320
25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 3 2 1 
K:321
25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 2 1 
K:322
25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 1 
K:323
25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 
K:324
25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:325
26 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:326
26 25 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:327
26 25 24 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:328
26 25 24 23 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:329
26 25 24 23 22 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:330
26 25 24 23 22 21 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:331
26 25 24 23 22 21 20 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:332
26 25 24 23 22 21 20 19 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:333
26 25 24 23 22 21 20 19 18 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:334
26 25 24 23 22 21 20 19 18 17 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:335
26 25 24 23 22 21 20 19 18 17 16 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:336
26 25 24 23 22 21 20 19 18 17 16 15 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:337
26 25 24 23 22 21 20 19 18 17 16 15 14 12 11 10 9 8 7 6 5 4 3 2 1 
K:338
26 25 24 23 22 21 20 19 18 17 16 15 14 13 11 10 9 8 7 6 5 4 3 2 1 
K:339
26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 10 9 8 7 6 5 4 3 2 1 
K:340
26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 9 8 7 6 5 4 3 2 1 
K:341
26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 8 7 6 5 4 3 2 1 
K:342
26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 7 6 5 4 3 2 1 
K:343
26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 6 5 4 3 2 1 
K:344
26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 5 4 3 2 1 
K:345
26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 4 3 2 1 
K:346
26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 3 2 1 
K:347
26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 2 1 
K:348
26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 1 
K:349
26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 
K:350
26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:351
27 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:352
27 26 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:353
27 26 25 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:354
27 26 25 24 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:355
27 26 25 24 23 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:356
27 26 25 24 23 22 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:357
27 26 25 24 23 22 21 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:358
27 26 25 24 23 22 21 20 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:359
27 26 25 24 23 22 21 20 19 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:360
27 26 25 24 23 22 21 20 19 18 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:361
27 26 25 24 23 22 21 20 19 18 17 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:362
27 26 25 24 23 22 21 20 19 18 17 16 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:363
27 26 25 24 23 22 21 20 19 18 17 16 15 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:364
27 26 25 24 23 22 21 20 19 18 17 16 15 14 12 11 10 9 8 7 6 5 4 3 2 1 
K:365
27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 11 10 9 8 7 6 5 4 3 2 1 
K:366
27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 10 9 8 7 6 5 4 3 2 1 
K:367
27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 9 8 7 6 5 4 3 2 1 
K:368
27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 8 7 6 5 4 3 2 1 
K:369
27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 7 6 5 4 3 2 1 
K:370
27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 6 5 4 3 2 1 
K:371
27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 5 4 3 2 1 
K:372
27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 4 3 2 1 
K:373
27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 3 2 1 
K:374
27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 2 1 
K:375
27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 1 
K:376
27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 
K:377
27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:378
28 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:379
28 27 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:380
28 27 26 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:381
28 27 26 25 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:382
28 27 26 25 24 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:383
28 27 26 25 24 23 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:384
28 27 26 25 24 23 22 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:385
28 27 26 25 24 23 22 21 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:386
28 27 26 25 24 23 22 21 20 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:387
28 27 26 25 24 23 22 21 20 19 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:388
28 27 26 25 24 23 22 21 20 19 18 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:389
28 27 26 25 24 23 22 21 20 19 18 17 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:390
28 27 26 25 24 23 22 21 20 19 18 17 16 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:391
28 27 26 25 24 23 22 21 20 19 18 17 16 15 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:392
28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 12 11 10 9 8 7 6 5 4 3 2 1 
K:393
28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 11 10 9 8 7 6 5 4 3 2 1 
K:394
28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 10 9 8 7 6 5 4 3 2 1 
K:395
28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 9 8 7 6 5 4 3 2 1 
K:396
28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 8 7 6 5 4 3 2 1 
K:397
28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 7 6 5 4 3 2 1 
K:398
28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 6 5 4 3 2 1 
K:399
28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 5 4 3 2 1 
K:400
28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 4 3 2 1 
K:401
28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 3 2 1 
K:402
28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 2 1 
K:403
28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 1 
K:404
28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 
K:405
28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:406
29 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:407
29 28 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:408
29 28 27 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:409
29 28 27 26 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:410
29 28 27 26 25 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:411
29 28 27 26 25 24 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:412
29 28 27 26 25 24 23 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:413
29 28 27 26 25 24 23 22 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:414
29 28 27 26 25 24 23 22 21 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:415
29 28 27 26 25 24 23 22 21 20 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:416
29 28 27 26 25 24 23 22 21 20 19 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:417
29 28 27 26 25 24 23 22 21 20 19 18 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:418
29 28 27 26 25 24 23 22 21 20 19 18 17 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:419
29 28 27 26 25 24 23 22 21 20 19 18 17 16 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:420
29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:421
29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 12 11 10 9 8 7 6 5 4 3 2 1 
K:422
29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 11 10 9 8 7 6 5 4 3 2 1 
K:423
29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 10 9 8 7 6 5 4 3 2 1 
K:424
29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 9 8 7 6 5 4 3 2 1 
K:425
29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 8 7 6 5 4 3 2 1 
K:426
29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 7 6 5 4 3 2 1 
K:427
29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 6 5 4 3 2 1 
K:428
29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 5 4 3 2 1 
K:429
29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 4 3 2 1 
K:430
29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 3 2 1 
K:431
29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 2 1 
K:432
29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 1 
K:433
29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 
K:434
29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:435
30 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:436
30 29 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:437
30 29 28 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:438
30 29 28 27 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:439
30 29 28 27 26 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:440
30 29 28 27 26 25 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:441
30 29 28 27 26 25 24 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:442
30 29 28 27 26 25 24 23 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:443
30 29 28 27 26 25 24 23 22 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:444
30 29 28 27 26 25 24 23 22 21 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:445
30 29 28 27 26 25 24 23 22 21 20 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:446
30 29 28 27 26 25 24 23 22 21 20 19 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:447
30 29 28 27 26 25 24 23 22 21 20 19 18 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:448
30 29 28 27 26 25 24 23 22 21 20 19 18 17 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:449
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:450
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:451
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 12 11 10 9 8 7 6 5 4 3 2 1 
K:452
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 11 10 9 8 7 6 5 4 3 2 1 
K:453
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 10 9 8 7 6 5 4 3 2 1 
K:454
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 9 8 7 6 5 4 3 2 1 
K:455
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 8 7 6 5 4 3 2 1 
K:456
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 7 6 5 4 3 2 1 
K:457
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 6 5 4 3 2 1 
K:458
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 5 4 3 2 1 
K:459
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 4 3 2 1 
K:460
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 3 2 1 
K:461
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 2 1 
K:462
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 1 
K:463
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 
K:464
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
K:465

- kc January 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

public class PrimeSubsets {
	public static void main(String[] args) {
		findPrimeSubsets();
	}
	
	public static void findPrimeSubsets() {
		int N = 100;
		int sum = (N * (N+1))/2;
		
		boolean [][] matrix = new boolean[N+1][sum+1];
		
		for (int i=0; i<=N; i++) {
			matrix[i][0] = true;
		}
		
		for (int j=1; j<=sum; j++) {
			matrix[0][j] = false;
		}
		
		for (int i=1; i<=N; i++) {
			for (int j=1; j<=sum; j++) {
				matrix[i][j] = matrix[i-1][j] || ((i<=j) && (matrix[i-1][j-i]));
			}
		}
		
		//int s = 299;
		for (int n=1; n<=sum; n++) {
		int k = 0;
		int s = n;
		for (int i=N; i>=1; i--) {
			if (!matrix[i-1][s]) {
				System.out.print(i + " ");
				k = k + i;
				s = s - i;
			}
		}
		System.out.println();
		System.out.println("K:" + k);
		}
		
		
//		for (int i=1; i<=sum; i++) {
//			System.out.println(i + ":" + matrix[N][i]);
//		}
	}
}

- kc January 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Ok, here we go. Use dynamic programming with the following relation:

F(x, k) =
x == A.length && isPrime(k): 1
x == A.length && !isPrime(k): 0
else: F(x+1, k+A[x]) + F(x+1, k)

The answer is F (0,0).

The interpretation of this is as follows: F(x,k) represents the number of ways to sum up to a prime if the sum so far is k and we are currently considering whether or not to include the x-th element. This number is the sum of the number of ways to get a prime when we include and when we don't include the x-th number in the sum. When there is no x-th number, there are no more choices to be made and the answer depends on whether the sum so far is a prime.

The time and space complexity are O(N^3) because k can be up to N^2/2 and x can be up to N. So there are O(N^3) states and O(1) work to be done per state, for a total time complexity of O(N^3). A trivial algorithm can precompute a boolean array representing which of the possible O(N^2) sums are prime for use in the base cases of the DP algorithm in O(N^3) time or less.

- eugene.yarovoi November 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@eugene: can you elaborate more on your solution ?

what do you denote by N in your complexity analysis ?
if we are just given consecutive numbers from 1 to N,
then certainly we can generate *all* sums from 1 to N(N+1)/2

if N is just the size of an array of arbitrary integers,
then I assume in your complexity analysis you should use
abs(A[1]) + abs(A[2]) + ... + abs(A[N]) for the estimate on 'k'

- Anonymous November 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We know the numbers are 1-N. At least that's how I understood the question. The trick is to count which of the 2^N subsets of these numbers sum to a prime number. The sum (k) is bounded by N(N+1)/2. x is bounded by N

- eugene.yarovoi November 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

aah, gotcha.. I somehow missed the point that we need to *count* the number of such subsets. thanks for update

- Anonymous November 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the number of subsets of [1..n] whose sum is 's'
is given by the coefficient of x^s in the polynomial:

F:=(1+x)*(1+x^2)*...*(1+x^n).

Example: n = 5
F:= 1+3*x^5+2*x^4+3*x^9+2*x^3+3*x^8+
3*x^7+2*x^12+x^2+3*x^6+2*x^11+3*x^10+x^14+x+x^13+x^15

thus the # of subsets which 
sum up to 3 is 2 (because F has a term 2*x^3)
sum up to 7 is 3 (F has a term 3*x^7)
sum up to 13 is 1 (F has a term x^13)
and so on..

we can compute the coeffs of F using 'shift-and-add'
approach, that is, start from (x + 1)
then shift this by 2 positions to the right and sum up
with the original coeffs: which is the same as multiplication by (x^2 + 1), and so on

- pavel.em November 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@asm: and then you'd check for primality on each number?

- eugene.yarovoi December 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yep that's right, I have no other soln in mind..
we cannot check for primality prematurely because,
so to say, smaller powers of x contribute to larger powers of x
even if they are composite similar to DP solution.

As we need to find all prime numbers in the range 1..n(n+1)/2
I guess the sieve of eratosthenes would work best..

- Anonymous December 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

Here you go:
This problem is essentially "find the number of primes from 1 - (1+N)*N/2" because the sum of all possible subsets can be only from 1 to (1+N)*N/2. Now it's much easier, below is the code in Java:

public static int primes(int n){
		if (n <= 1) return 0;
		int total = (1+n)*n/2;
		int m = (int) Math.sqrt(total);
		boolean[] prime = new boolean[total+1];
		Arrays.fill(prime, true);
		prime[0] = false;
		prime[1] = false;
		for (int i = 2; i <= m; i++){
			if (prime[i]){
				for (int k = i*i; k <= total; k += i){
					prime[k] = false;
				}	
			}
		}
		int totalPrimes = 0;
		for (boolean boo: prime){
			if (boo)
				totalPrimes++;
		}
		return totalPrimes;
	}

- kevinwangjiakan December 03, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This need not be contigious

- P December 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I never assumed numbers in subsets should be *contiguous.

- kevinwangjiakan December 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your code is correct to calculate the # of prime numbers between 1 and N(N+1)/2 but not to calculate the # of subsets, since we can obtain a prime number from more than 1 subset. For example, 7 can be obtained from (7), (1,6), (2,5), (3,4), (1,2,4).

- Sergi January 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This code is to calculate number of primes and the method used is called Sieve of Eratosthenes.

- Bhaskar August 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1 approach could be generate all subsets and check if sum is prime .
but i think there will be a better approach to do this.

- techcoder November 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, there's a better approach.

- eugene.yarovoi November 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Straight brute force is 2^n.
I think it is dynamic:
So ,
F(k)=F(k-1)+{1 if k is prime
0 if k is non prime}

- nitin November 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Dynamic programming would work, but your recurrence is not right.

- eugene.yarovoi November 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You missed a lot of subsets here.

- Anonymous November 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assumptions:
* By subset of [1-n], you can use an element only once.

Logic:
* I don't see any reason why prime numbers are targeted, but you can generalize to any number. i.e. Given set [1-n] and m, find number of sub-sets that add upto m.

Solution:
Now consider the notation F(m, n): Number of sub-sets of [1-n] that add upto m.
We have "F(m, n) = sigma (i goes from n to 1) {F(m - i, i - 1)}"
F(m, n) = 0 if "n < 1" or "m > nx(n+1)/2". This way you can calculate using memoization/DP with a matrix of size nxm in O(nm).

Now coming back to the question. You have to find the following:
sigma {F(p, n)} for all primes p <= nx(n+1)/2.
Therefore you have to compute F(P,n), where P is the max prime number < nx(n+1)/2 in O(nP) ~ O(n^3).

- kartikaditya November 29, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You recurrence looks good

- Anonymous November 29, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Do we need to count sigma(i goes from n to 1)?
if so your method is O(n^4)

- tc December 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@tc he said memoization

- Sem March 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isPrime(int n)
{
    if (n == 2) return true;

    if ((n & 1) == 0) return false;

    int s = (int)sqrt((doulbe)n);

    for (int i = 3; i <= s; i+=2)
    {
        if (n % i == 0)
        {
            return false;
        }
    }

    return true;
}

int primeSumSubsetCount(int n)
{
    int maxSumPossilbe = (n * (n + 1)) / 2;

    // let a[i][s] equal the count of the ways sum 's' can be produced from 1..i.
    // range for i is 1 .. n and range for s is 1 ... maxSumPossilbe.

    int **a = new int * [n + 1];
    for (int i = 0; i <= n; ++i)
    {
        a[i] = new int [maxSumPossilbe + 1];
        memset(a[i], 0,  (maxSumPossilbe + 1) * sizeof(int));
    }

    a[0][0] = 1;

    // a[i][s] = a[i-1][s] + a[i-1][s-i].
    for (int i = 1; i <= n; ++i)
        for (int s = 1; s <= maxSumPossilbe; ++s)
        {
            a[i][s] = a[i-1][s];

            if (s-i > 0)
            {
                a[i][s] += a[i-1][s-i];
            }
        }

    int primesCount = 0;

    if (maxSumPossilbe >= 2)
    {
        primesCount = a[n][2];
    }

    for (int s = 3; s <= maxSumPossilbe; s += 2)
    {
        if (isPrime(s))
        {
            primesCount += a[n][s];
        }
    }

    for (int i = 0; i <= n; ++i)
    {
        delete []a[i];
    }

    delete []a;

    return primesCount;
}

- Anonymous November 29, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This program does not appear to give the right answer for n = 6. The answer it gives is 0. Thank you.

- camster December 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can compute a list on the number of sum of subsets, e.g.
lst3 = [0, 1, 1, 2, 1, 1, 1], where lst3[2] = number of subsets sum equal to 2, when n = 3.
we can use lst3 to compute lst4, and so on. This part will take n*nC2 = O(n^3). Calculating primes seems needs O(nlogn) anyways. So the total complexity is O(n^3).

import math

_cache = {}
def _sumTo(n):
    if n in _cache:
        return _cache[n]

    if n == 0 or n == 1:
        return n
    _cache[n] = n + _sumTo(n-1)
    return _cache[n]

def _numOfSubsetSum(n):
    lst = [0] * (_sumTo(n)+1) # easy indexing

    for i in range(1, n+1):
        for s in reversed(range(1, _sumTo(i-1)+1)):
            lst[i + s] += lst[s]
        lst[i] += 1
    return lst

def _primesLessThan(n):
    if n < 2:
        return []
    primes = [2]
    for i in range(3, n+1, 2):
        sqrtI = int(math.sqrt(i))
        for p in primes:
            if i % p == 0:
                break
            if p > sqrtI:
                primes.append(i)
                break
    return primes

def numOfSubsetSumEqPrime(n):
    """ n is size of set """
    lst = _numOfSubsetSum(n)
    maxPossibleSum = _sumTo(n)
    return sum(lst[i] for i in _primesLessThan(maxPossibleSum))

if __name__ == "__main__":
    print numOfSubsetSumEqPrime(10)

- tc December 08, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is a direct Knapsack problem

- Aravind November 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

??? How?
Assume we have 1 7 3, 4
{1, 7} is not a subset which sum is prime. However, after we put 3 there, we get {1, 7 ,3} which sum is prime.

- Anonymous November 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, in knapsack every possible case gets covered, so this case will also get covered. Just some memorization is done in knapsack.

- ishantagarwal1986 November 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

hmm I doubt this is a knapsack problem..
this more looks like a modification of subset sum problem.

that is, we need to allocate a boolean array 'B[0..S]'
where 'S' is the maximal prime number <= sum(|a[i]|,i=1..N)
and a[N] - is the array of numbers.

such that B[s] == true if there is a subset of a[N] which sums up to 's'. Then proceed with the usual DP solution. Complexity: O(N*S). Of cource, at the end we also need to perform primality check which can take additional time

- Anonymous November 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Naturally we can produce all the sums because the input is all the numbers from 1 to N. Given 1,2,3,4,5. we will be able to produce all the sums from 1 to 15.
Am I considering something wrong here. IS the input from 1 to N or just N random integers.

- Anonymous November 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

its a straight bruteforce, nothing much do it with looping or recursion, or if n is under range one may go for bitmasking.

- noname.cpp November 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is, in fact, a modification of the subset-sum problem. There are 2 differences:

1) You must modify the algorithm to count the number of ways to sum to a target number
2) You must make there not be a single target number but any number belonging to a set (here, the set of primes)

- eugene.yarovoi November 22, 2011 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More