TopCoder Statistics - Problem Statement

Problem Statement

Paola has an array of integers. The array is called A and its length is n. The elements of A have indices between 0 and n-1, inclusive.

Paola's favorite number is the long p. Can Paola multiply two elements of her array to get the product p?

If there are two (not necessarily distinct) indices i, j into Paola's array such that A[i] * A[j] = p, return the int[] {i, j}. (I.e., a int[] with two elements, the first of which is i and the second of which is j.) If there are multiple solutions, you may return any one of them. If there is no solution, return an empty int[] instead.

In order to keep the input size small, you are not given Paola's array explicitly. Instead, you have to generate it using some very simple pseudocode. You are given the ints n, a0, and step. Generate Paola's array as follows:

A[0] = a0
for i = 1 .. n-1:
    A[i] = A[i-1] + step

Definition

Class:: PairProduct
Method:: findPair
Parameters:: int, int, int, long
Returns:: int[]
Method signature:: int[] findPair(int n, int a0, int step, long p)
(be sure your method is public)

Notes

This problem does have general solutions that work for any array A of the given size. Using the special form of the values in the array is not necessary.

Constraints

n will be between 1 and 100,000, inclusive.
a0 will be between -10^9 and 10^9, inclusive.
step will be between -10^9 and 10^9, inclusive.
a0 and step will be such that all elements of A will be between -10^9 and 10^9, inclusive.
p will be between -10^18 and 10^18, inclusive.

Examples

6

2

5

14

Returns: {0, 1 }

Paola's array is A = {2, 7, 12, 17, 22, 27}. The number 14 is the product of A[0] and A[1]. Note that {1, 0} is also a valid return value.
6

2

5

144

Returns: {2, 2 }

The indices into A don't have to be distinct.
6

2

5

47

Returns: { }

No two elements of this array have the product 47.
6

-200000

-500000

2040000000000

Returns: {2, 3 }

This time Paola's array is {-200000, -700000, -1200000, -1700000, -2200000, -2700000}. The value 2040000000000 is A[2] * A[3]. Watch out for integer overflow.
20

-5

1

-6

Returns: {2, 7 }

The desired product p may be negative. In this case, A = {-5,-4,-3,...,14} and the returned value corresponds to the fact that A[2] * A[7] = (-3) * 2 = (-6). There are other correct answers as well.
20

-5

1

0

Returns: {5, 5 }
1

0

47

0

Returns: {0, 0 }
100000

0

0

0

Returns: {0, 0 }
100000

0

0

1

Returns: { }
100000

0

0

-1

Returns: { }
100000

2

1

1

Returns: { }
100000

722004112

10

522039811160593824

Returns: {4348, 99506 }
100000

-13033

1

0

Returns: {13033, 13033 }
100000

-251147556

-100

-8524211560286888

Returns: { }
100000

-95520

10

0

Returns: {9552, 9552 }
100000

42385974

5

1809325506661576

Returns: {1990, 58180 }
100000

-409519030

10000

206645634256140900

Returns: {75989, 99931 }
100000

-47

0

2209

Returns: {0, 99999 }
100000

452640682

-50

201397621624650924

Returns: {61840, 92822 }
100000

406647323

-10000

-104646528473803671

Returns: {7062, 71807 }
100000

722004112

10

73286783806858534

Returns: { }
100000

-855765286

100

728731373577874596

Returns: {18406, 23746 }
100000

-855765286

100

715846773885125796

Returns: {96880, 96880 }
100000

794808693

1000

681522389052078249

Returns: {30735, 30735 }
100000

406647323

-10000

11541803566329

Returns: {40325, 40325 }
100000

-409519030

10000

-102874365336359100

Returns: {10576, 74819 }
100000

722004112

10

522116165490377384

Returns: {34734, 79663 }
100000

-157294345

1

24738911249671665

Returns: {3100, 13428 }
100000

816367118

-4

665935253679042860

Returns: {61737, 97540 }
100000

-848617825

-1

0

Returns: { }
100000

143754

-2

0

Returns: {71877, 71877 }
100000

781658391

-1000

510674600354428881

Returns: {64839, 69241 }
100000

887959676

4

788842169083951632

Returns: {31322, 72778 }
100000

-480204100

2

230458674039187888

Returns: {49041, 93942 }
17

-997868077

123456789

729288258927802564

Returns: {15, 15 }
100000

42385974

5

1816251812383316

Returns: {19555, 73142 }
100000

-73065678

50

5183327438063584

Returns: {16760, 26039 }
100000

242001581

3

58635752073285688

Returns: {12725, 85039 }
100000

887959676

4

788760359430337840

Returns: {34286, 46784 }
100000

-480204100

2

230521181387438736

Returns: {4358, 73523 }
100000

816367118

-4

-6250182107152840

Returns: { }
100000

452640682

-50

203444372275878724

Returns: {31852, 31852 }
100000

-157294345

1

24727977638691040

Returns: {5360, 80681 }
100000

970309599

-2

941239284200566129

Returns: {67363, 67363 }
100000

781658391

-1000

-207185372739983255

Returns: { }
100000

-660235892

-2

0

Returns: { }
100000

970309599

-2

78191478241249762

Returns: { }
100000

-157294345

1

-24083210393580390

Returns: { }
100000

242001581

3

42056479114130916

Returns: { }
100000

-409519030

10000

46468365365590267

Returns: { }
100000

-73065678

50

4924696317969784

Returns: {24118, 90673 }
100000

235324427

-3

55288975494893329

Returns: {25686, 99862 }
100000

42385974

5

1820432101645496

Returns: {33178, 79103 }
100000

816367118

-4

665937782031012100

Returns: {79252, 79252 }
100000

970309599

-2

941307161338565249

Returns: {31160, 68584 }
17

-997868077

123456789

368534203445232400

Returns: {13, 13 }
100000

970309599

-2

941333425831919451

Returns: {30151, 56058 }
100000

-73065678

50

5244769086125284

Returns: {12898, 12898 }
100000

-244315921

-1

-4030398852352815

Returns: { }
100000

47

0

0

Returns: { }
100000

722004112

10

522510072499410724

Returns: {84447, 84447 }
100000

452640682

-50

203106844044354624

Returns: {2913, 75617 }
100000

-403513211

-1234

0

Returns: { }
100000

235324427

-3

55362711064226314

Returns: {4623, 16448 }
100000

415239213

10

0

Returns: { }
100000

75350

-10

0

Returns: {7535, 7535 }
100000

816367118

-4

666218433976684356

Returns: {28645, 43889 }
17

993982394

-123456789

-1522444746698672

Returns: {8, 10 }
100000

42385974

5

1806043370909761

Returns: {22319, 22319 }
100000

-244315921

-1

59706756830814921

Returns: {33740, 33740 }
100000

208970986

-5

43637675016298276

Returns: {14932, 14932 }
100000

-855765286

100

728904584250430396

Returns: {5465, 34634 }
100000

-73065678

50

4922791315174144

Returns: { }
100000

794808693

1000

701884653185818249

Returns: {6118, 81532 }
100000

-480204100

2

90948318089801475

Returns: { }
100000

816367118

-4

666229813163870076

Returns: {14436, 54611 }
100000

452640682

-50

202064349614442624

Returns: {41285, 83665 }
100000

47

0

2209

Returns: {0, 99999 }
100000

-47

0

-2209

Returns: { }
100000

208970986

-5

43555636902243821

Returns: {28957, 79473 }
100000

-251147556

-100

64537862227148336

Returns: {58, 58184 }
100000

-1650

2

0

Returns: {825, 825 }
100000

235324427

-3

55315806517651876

Returns: {43767, 43767 }
100000

781658391

-1000

511168577249415881

Returns: {59452, 73871 }
100000

-244315921

-1

59706047149635075

Returns: {8194, 56384 }
17

993982394

-123456789

539361943417673104

Returns: {14, 14 }
100000

406647323

-10000

92592470271566329

Returns: {2910, 16140 }
100000

-106705214

1234

0

Returns: {86471, 86471 }
100000

452640682

-50

-5448716734111028

Returns: { }
100000

-480204100

2

230464946658257696

Returns: {46326, 90124 }
100000

-244315921

-1

59719549243139226

Returns: {45018, 74813 }
100000

242001581

3

58640241445193185

Returns: {33138, 70794 }
17

-997868077

123456789

-542287720858880606

Returns: { }
100000

887959676

4

788509723572490000

Returns: {5256, 5256 }
100000

970309599

-2

941276097725356875

Returns: {41362, 74391 }
100000

-349879470

-10

0

Returns: { }
100000

235324427

-3

55288063662615634

Returns: {31275, 95570 }
100000

13831906

-1234

0

Returns: {11209, 11209 }
100000

-480204100

2

230444699767833600

Returns: {78770, 78770 }
100000

781658391

-1000

551940575970520881

Returns: {1308, 74360 }
100000

781658391

-1000

476873653618072881

Returns: {91098, 91098 }
100000

242001581

3

58649663854188700

Returns: {50275, 66623 }
100000

728290065

-10

371565487414807261

Returns: { }
17

-997868077

123456789

-641302945143027242

Returns: {2, 15 }
100000

-818618729

1

0

Returns: { }
100000

208970986

-5

43497903269787041

Returns: {68077, 95709 }
100000

728290065

-10

529324726471329325

Returns: {67007, 81593 }
100000

66783

-1

0

Returns: {66783, 66783 }
100000

235324427

-3

-3087028708297046

Returns: { }
17

993982394

-123456789

-665985226996983663

Returns: { }
100000

-251147556

-100

67444846248519936

Returns: {85539, 85539 }
17

-997868077

123456789

806543353728643398

Returns: { }
100000

728290065

-10

530081577199777725

Returns: {9777, 34831 }
100000

406647323

-10000

2866924282826329

Returns: {11610, 39678 }
100000

-409519030

10000

-20691330227459100

Returns: {35802, 81130 }
100000

-855765286

100

727961551171408596

Returns: {2715, 48397 }
100000

728290065

-10

529600644958727925

Returns: {10848, 99806 }
17

993982394

-123456789

237655347150857476

Returns: {12, 12 }
100000

748826206

1234

0

Returns: { }
100000

887959676

4

788983660265695584

Returns: {69819, 74104 }
100000

-73065678

50

5032611480218784

Returns: {23156, 61575 }
100000

406647323

-10000

-177728279295897851

Returns: { }
100000

242001581

3

58607964644090761

Returns: {29746, 29746 }
100000

-157294345

1

24719308574262291

Returns: {54856, 86326 }
100000

-251147556

-100

66138277638624336

Returns: {51426, 69126 }
100000

-244315921

-1

59722529867040138

Returns: {59462, 72565 }
100000

794808693

1000

736867352385660249

Returns: {44346, 83298 }
100000

794808693

1000

705424674695727249

Returns: {19734, 71229 }
100000

208970986

-5

11075768896910708

Returns: { }
100000

-251147556

-100

64314238696518336

Returns: {14165, 34977 }
100000

-855765286

100

-268517534633000294

Returns: { }
100000

-409519030

10000

107814359499940900

Returns: {73787, 73787 }
100000

-157294345

1

24741485487301696

Returns: {81, 81 }
100000

42385974

5

985256700409300

Returns: { }
17

993982394

-123456789

742573250210425504

Returns: {0, 2 }
100000

887959676

4

-69283395957452050

Returns: { }
100000

208970986

-5

43579118178708651

Returns: {34109, 51835 }
100000

722004112

10

522048395059362864

Returns: {47916, 57095 }
100000

-19436885

2

0

Returns: { }
100000

794808693

1000

-659482178283924411

Returns: { }
100000

728290065

-10

529362899597157025

Returns: {71677, 71677 }
10

0

0

0

Returns: {0, 0 }
5

0

0

5

Returns: { }
10

0

1

2

Returns: {1, 2 }
100000

0

1

100000000000000000

Returns: { }
1

1000000000

1

1000000000000000000

Returns: {0, 0 }
100000

1

0

100000

Returns: { }
100000

10

10

10000

Returns: {0, 99 }
6

0

0

20

Returns: { }
100000

1

1

-1

Returns: { }
2

0

0

0

Returns: {0, 0 }
5

10

0

100

Returns: {0, 4 }
1

10

10

1001

Returns: { }
100000

1

1

9999700002

Returns: {99997, 99998 }
100000

1

1

1000000000000000000

Returns: { }
111

0

0

0

Returns: {0, 0 }
100000

0

1

0

Returns: {0, 0 }
1

2

0

5

Returns: { }
4

1

1

9

Returns: {2, 2 }
111

0

1

5

Returns: {1, 5 }
2

2

2

13

Returns: { }
5

-4

2

10

Returns: { }
20

0

1

10

Returns: {1, 10 }
100

0

0

1000

Returns: { }
5

5

0

25

Returns: {0, 4 }
100000

-99999

1

1

Returns: {99998, 99998 }
100000

-1000

1

1000000007

Returns: { }
2

5

-5

1

Returns: { }
1

0

0

0

Returns: {0, 0 }
1

0

1

0

Returns: {0, 0 }
100000

0

0

1000007

Returns: { }
5

-7

5

14

Returns: {0, 1 }
3

0

1

2

Returns: {1, 2 }
7

0

1

9

Returns: {3, 3 }
100000

0

1

-1

Returns: { }

Statistics

Problem Statement for "PairProduct"

Problem Statement

Definition

Notes

Constraints

Examples