Problem Statement
An arithmetic sequence of length n is a sequence of n numbers in which the difference between each pair of adjacent numbers is some constant delta. For example, the sequence 1,6,11,16 is an arithmetic sequence of length 4 with delta=5. Now, consider the infinite set
{ 1, 3, 4, 7, 8, 9, ... }
This set is of particular interest to mathematicians because it contains arbitrarily long arithmetic sequences for any delta, yet it contains no infinitely long arithmetic sequences. The set is contructed by keeping or dropping successive groups of positive integers according to the following pattern: keep one (1), drop one (2), keep two (3,4), drop two (5,6), keep three (7,8,9), drop three (10,11,12), and so on.
Given n and delta, your task is to find the earliest arithmetic sequence contained in the set that has the given length and delta. In other words, you should find the smallest number A such that all integers of the form A+i*delta are in the set, for all i between 0 and n-1, inclusive. You should return A.
Definition
- Class:
- ArithSeq
- Method:
- minStart
- Parameters:
- int, int
- Returns:
- long
- Method signature:
- long minStart(int n, int delta)
- (be sure your method is public)
Constraints
- n is between 2 and 30, inclusive.
- delta is between 1 and 100000000, inclusive.
Examples
3
3
Returns: 1
The sequence is 1, 4, 7.
5
12
Returns: 9
6
12
Returns: 3661
30
4130
Returns: 1001001
30
100000000
Returns: 670380219057
30
100
Returns: 8412901
30
4127
Returns: 1001001
30
421
Returns: 149071891
30
422
Returns: 38613
30
449
Returns: 169559463
30
3365
Returns: 2687961
30
3366
Returns: 660157
5
197073
Returns: 1
6
12345678
Returns: 34411
20
1010101
Returns: 70790917
23
100000000
Returns: 37200659057
23
98765432
Returns: 36568808127
2
1
Returns: 3
30
1
Returns: 871
20
19
Returns: 130683
5
5
Returns: 421
10
20
Returns: 32581
20
10
Returns: 36291
8
72788984
Returns: 362359
9
23943966
Returns: 159601
17
70943590
Returns: 45304041
14
49708334
Returns: 14173803
17
75093584
Returns: 18100771
9
92268860
Returns: 636147
17
35773335
Returns: 278954098
26
99727298
Returns: 536457367057
20
98294672
Returns: 4939276741
22
45307202
Returns: 12794700279
20
47871914
Returns: 10449872309
9
77995986
Returns: 307471
25
16297485
Returns: 45786370507
21
5558261
Returns: 8525475223
26
82361186
Returns: 412991953381
29
90794986
Returns: 552581859523
15
11975572
Returns: 113565249
11
51005214
Returns: 1637857
19
13364526
Returns: 503952219
25
25314000
Returns: 82439904253
29
27691612
Returns: 113650905763
17
14862332
Returns: 1882496821
26
36149331
Returns: 141332763307
15
6811730
Returns: 1066057
27
40799902
Returns: 172790278081
26
64698373
Returns: 299811550051
28
68352792
Returns: 358575212533
26
4878565
Returns: 10265438443
4
53583664
Returns: 27723
15
81639339
Returns: 14061810
4
82244019
Returns: 31153
6
72005180
Returns: 121671
9
12080287
Returns: 202429
24
85353684
Returns: 30036254035
17
44975677
Returns: 4458729102
11
22660161
Returns: 78681
19
93247632
Returns: 11939918317
14
75523134
Returns: 12716335
30
57951147
Returns: 321937653421
30
68778248
Returns: 404544973483
30
92187448
Returns: 588829859257
30
86079769
Returns: 549385593231
30
72640132
Returns: 435009500257
30
24924546
Returns: 107179301307
30
34526845
Returns: 160673908123
30
85502222
Returns: 542035349131
30
48670653
Returns: 256313869351
30
98050053
Returns: 644475798057
30
65164912
Returns: 376970826421
30
100000000
Returns: 670380219057
9
3144
Returns: 81