TopCoder Statistics - Problem Statement

Problem Statement

Your task is to find the minimal positive integer x such that:
1. x is an integer multiple of N.
2. The decimal representation of x doesn't contain any forbidden digits.
You will be given the forbidden digits as a int[] forbiddenDigits.

If there is no solution, you should return the String "IMPOSSIBLE" (quotes for clarity).
If there is a solution and its number of digits is strictly less than 9, you should return a String containing the integer x in base 10, with no leading zeros.
Otherwise, you should return a String of the form "abc...def(g digits)" (quotes for clarity). In the return value, abc are the first three digits of the smallest valid integer x, def are its last three digits, and g is the number of digits in x (a base-10 integer with no leading zeros).

Definition

Class:: MultiplesWithLimit
Method:: minMultiples
Parameters:: int, int[]
Returns:: String
Method signature:: String minMultiples(int N, int[] forbiddenDigits)
(be sure your method is public)

Constraints

N will be between 1 and 10000, inclusive.
forbiddenDigits will contain between 0 and 10 elements, inclusive.
Each element of forbiddenDigits will be between 0 and 9, inclusive.
The elements of forbiddenDigits will be pairwise distinct.

Examples

8

{2,3,4,5,6,7,8,9}

Returns: "1000"

The smallest positive multiple of 8 that only contains digits 0 and 1 is 1000.
9

{1,3,4,5,6,7,8,9}

Returns: "222...222(9 digits)"
524

{5,2,4}

Returns: "3668"
10000

{0}

Returns: "IMPOSSIBLE"
1

{0,1,2,3,4,5,6,7,8,9}

Returns: "IMPOSSIBLE"
2007

{1,2,3,4,5,6,8,9,0}

Returns: "777...777(666 digits)"
100

{1,2,3}

Returns: "400"
200

{3,4,5}

Returns: "200"
862

{1,4,6,7,8}

Returns: "99992"
7048

{1,4,5,6,7,9}

Returns: "2332888"
4261

{0,2,3,5,6,7,8}

Returns: "9199499"
6867

{0,4,5,7}

Returns: "96138"
9543

{0,1,2,3,5,8}

Returns: "6479697"
7341

{1,2,3,5,7,9}

Returns: "44046"
7008

{3,5,6,7,8}

Returns: "21024"
4064

{0,4,5,6,8,9}

Returns: "337312"
5194

{4,5,7}

Returns: "10388"
4074

{1,2,4,5,6}

Returns: "387030"
8794

{1,2,3,5,6,7,8,9}

Returns: "444...404(14 digits)"
9723

{1,2,3,8,9}

Returns: "466704"
1940

{0,3,4,8,9}

Returns: "IMPOSSIBLE"
824

{1,3,4,8,9}

Returns: "20600"
9799

{4,7}

Returns: "19598"
9334

{1,2,3,6,8}

Returns: "700050"
5310

{0,1,4,6,9}

Returns: "IMPOSSIBLE"
1926

{2,4,8,9}

Returns: "11556"
2421

{0,6,8,9}

Returns: "2421"
1719

{0,1,2,4}

Returns: "6876"
3778

{2,3,8}

Returns: "7556"
4990

{0,3,8,9}

Returns: "IMPOSSIBLE"
5570

{0,3,4,7,8,9}

Returns: "IMPOSSIBLE"
5334

{0,1,2,4,6,7,8,9}

Returns: "IMPOSSIBLE"
4892

{0,3,4,9}

Returns: "78272"
8712

{0,8,9}

Returns: "17424"
2568

{2,3,4,8,9}

Returns: "115560"
3432

{1,3,5,8}

Returns: "24024"
2821

{1,2,3,4,5,6,8,9}

Returns: "777...777(9 digits)"
7531

{0,3,5}

Returns: "67779"
1630

{2,5,6,7,9}

Returns: "11410"
4433

{1,2,5,7,8,9}

Returns: "4433"
1818

{0,4,6,8}

Returns: "7272"
6221

{1,4,5,6}

Returns: "80873"
3516

{1,9}

Returns: "7032"
7220

{2,3,4,5,9}

Returns: "101080"
9327

{1,3,4,5,8,9}

Returns: "22767207"
6143

{0,3,5,6,7}

Returns: "18429"
76

{1,6,7,8,9}

Returns: "304"
5052

{1,3,5,6}

Returns: "20208"
2818

{0,1,3,4,5,6,8}

Returns: "22977972"
4910

{0,3,4,5,7,8,9}

Returns: "IMPOSSIBLE"
3336

{0,1,7,8,9}

Returns: "3336"
1247

{3,5,7,8}

Returns: "2494"
7268

{0,2,3,5}

Returns: "79948"
2102

{0,2,3,4,8,9}

Returns: "5166716"
7664

{0,1,9}

Returns: "7664"
9416

{2,6,7}

Returns: "404888"
2034

{0,1,3,5,7,8}

Returns: "26442"
8490

{0,2,3,7,8,9}

Returns: "IMPOSSIBLE"
1949

{0,1,5,6,7,9}

Returns: "23388"
3845

{1,2,3,4,6,7,8,9}

Returns: "500...005(12 digits)"
7262

{5}

Returns: "7262"
9787

{1,6,7,8}

Returns: "342545"
631

{0,1,3,6,8,9}

Returns: "2524"
2660

{0,5,7,8}

Returns: "IMPOSSIBLE"
9847

{0,2,7,8}

Returns: "19694"
2561

{4,6,7,9}

Returns: "5122"
7011

{0,1,2,4,5,6,7}

Returns: "33393393"
4155

{0,1,2,6,7,8}

Returns: "494445"
2969

{3,4,5,6,9}

Returns: "112822"
8655

{0,2,6,7,9}

Returns: "354855"
7782

{3,4,5,8,9}

Returns: "101166"
1569

{0,1,2,3,6,7}

Returns: "589944"
268

{3,4,5,6,7,8}

Returns: "9112"
9736

{2,3,4,5,7,8}

Returns: "6669160"
686

{1,2,3,4,5,7}

Returns: "686"
197

{1,2,3}

Returns: "788"
9316

{2,3,4,7,9}

Returns: "680068"
9646

{1,4,8,9}

Returns: "67522"
1809

{0,2,4,5,6,7,9}

Returns: "3133188"
1752

{1,7,8}

Returns: "3504"
5422

{0,2,4,5,8,9}

Returns: "1371766"
2289

{1,2,4,5,8,9}

Returns: "670677"
471

{0,3,4,7,8}

Returns: "5652"
1083

{4,7,8}

Returns: "2166"
6436

{3,4,5,6,7}

Returns: "180208"
5073

{0,1,2,3,6,7,9}

Returns: "4555554"
263

{0,1,2,3,6,8}

Returns: "4997"
5288

{2,3,4,6,7,9}

Returns: "185080"
4677

{0,1,5}

Returns: "4677"
8681

{0,1,4,6,7,8}

Returns: "3229332"
4309

{4,5,7,8,9}

Returns: "30163"
1227

{0,3,4,5,6,7,8}

Returns: "9112929"
8610

{0,1,3,4,9}

Returns: "IMPOSSIBLE"
3434

{1,2,4,5,6,8}

Returns: "703970"
9974

{0,1,3,5,8}

Returns: "9974"
9565

{2,4,5}

Returns: "19130"
3904

{6,8}

Returns: "3904"
9704

{1,2,4,5,7}

Returns: "698688"
4784

{0,1,2,4,9}

Returns: "368368"
4485

{6,9}

Returns: "4485"
4774

{3,5,6,8}

Returns: "4774"
2060

{0,1,5,6,8,9}

Returns: "IMPOSSIBLE"
1380

{1,3,4,7,8,9}

Returns: "5520"
4477

{4,5,6}

Returns: "17908"
2115

{0,1,2,3,4,5,8,9}

Returns: "IMPOSSIBLE"
8757

{2,3,6,7,8}

Returns: "499149"
560

{2,6,9}

Returns: "4480"
262

{0,1,2,3,7,8,9}

Returns: "4454"
9981

{0,2,3,4,5,6,7,8,9}

Returns: "111...111(9972 digits)"
1

{9,8,7,6,5,4,3,2,1}

Returns: "IMPOSSIBLE"
1

{0,1,2,3,4,5,6,7,8}

Returns: "9"
1

{}

Returns: "1"
5

{5}

Returns: "10"
4

{4,8}

Returns: "12"
3

{3,6,9}

Returns: "12"
8

{2,4,6,8}

Returns: "1000"
9

{1,2,3,4,5,6,9}

Returns: "77778"
9

{1,2,3,4,5,6,7,9}

Returns: "888...888(9 digits)"
9

{0,1,2,3,4,5,6,7,9}

Returns: "888...888(9 digits)"
10000

{}

Returns: "10000"
625

{5}

Returns: "10000"
999

{9}

Returns: "111888"
7999

{9}

Returns: "1007874"
9999

{9}

Returns: "11118888"
399

{8,9}

Returns: "10374"
998

{8,9}

Returns: "111776"
3999

{8,9}

Returns: "1011747"
9998

{8,9}

Returns: "11117776"
172

{2,4,6}

Returns: "11008"
996

{2,4,6}

Returns: "301788"
1992

{2,4,6}

Returns: "1770888"
9996

{2,4,6}

Returns: "30017988"
8192

{2,4,6,8}

Returns: "100...000(14 digits)"
8192

{1,2,4,6,8}

Returns: "300...000(14 digits)"
8192

{1,2,3,4,6,8}

Returns: "500...000(14 digits)"
7992

{2,3,4,6,7,8,9}

Returns: "111...000(18 digits)"
9999

{1,2,3,5,6,7,9}

Returns: "444...888(20 digits)"
7992

{1,2,3,4,5,6,8,9}

Returns: "777...000(30 digits)"
9999

{1,2,3,4,5,6,7,9}

Returns: "888...888(36 digits)"
9927

{0,1,2,3,4,5,6,7,9}

Returns: "888...888(9918 digits)"
9931

{0,1,2,3,4,5,6,7,8}

Returns: "999...999(9930 digits)"
9949

{0,1,2,3,4,5,6,7,8}

Returns: "999...999(9948 digits)"
9967

{0,1,2,3,4,5,6,7,8}

Returns: "999...999(9966 digits)"
8

{2, 3, 4, 5, 6, 7, 8, 9 }

Returns: "1000"
524

{5, 2, 4 }

Returns: "3668"
8

{ }

Returns: "8"
9

{1, 3, 4, 5, 6, 7, 8, 9 }

Returns: "222...222(9 digits)"
8786

{1, 3, 5, 6, 9 }

Returns: "70288"
8192

{2, 3, 4, 5, 6, 7, 8, 9 }

Returns: "100...000(14 digits)"
1

{ }

Returns: "1"
4433

{0, 2, 4, 6, 8, 9, 3, 5 }

Returns: "777...777(10 digits)"
9999

{0, 2, 3, 4, 5, 6, 7, 8, 9 }

Returns: "111...111(36 digits)"
81

{0, 1, 3, 4, 5, 6, 7, 8, 9 }

Returns: "222...222(81 digits)"
6561

{1, 3, 4, 5, 6, 7, 8, 9 }

Returns: "200...202(13 digits)"
81

{2, 3, 4, 5, 6, 7, 8, 9 }

Returns: "111...101(10 digits)"
9997

{0, 2, 3, 4, 5, 6, 7, 8, 9 }

Returns: "111...111(192 digits)"
2121

{0, 1, 2, 3, 4, 5, 6, 7, 8 }

Returns: "999...999(12 digits)"
9999

{2, 3, 4, 5, 6, 7, 8, 9, 0 }

Returns: "111...111(36 digits)"
1

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

Returns: "IMPOSSIBLE"
27

{1, 3, 4, 5, 6, 7, 8, 9 }

Returns: "220...222(10 digits)"
2

{1, 2, 3, 4, 5, 6, 7, 8, 9 }

Returns: "IMPOSSIBLE"
2

{0, 2, 3, 4, 5, 6, 7, 8, 9 }

Returns: "IMPOSSIBLE"
9

{0 }

Returns: "9"
9999

{9 }

Returns: "11118888"
9

{1, 2, 3, 4, 5, 6, 7, 9, 0 }

Returns: "888...888(9 digits)"
6561

{7 }

Returns: "6561"
9999

{1, 2, 3, 5, 6, 7, 8, 9 }

Returns: "444...444(36 digits)"
5

{0, 5 }

Returns: "IMPOSSIBLE"
999

{1, 2, 3, 4, 5, 6 }

Returns: "999"
1

{0, 1, 2, 3, 4, 5, 6, 7 }

Returns: "8"
10000

{0 }

Returns: "IMPOSSIBLE"
9

{0, 1, 3, 4, 5, 6, 7, 8, 9 }

Returns: "222...222(9 digits)"
99

{0, 1, 3, 4, 5, 6, 7, 8, 9 }

Returns: "222...222(18 digits)"
9091

{1, 4, 5, 6, 7, 8, 9, 0 }

Returns: "222...222(10 digits)"
9116

{2, 3, 4, 5, 6, 7, 8, 9 }

Returns: "100...100(15 digits)"
999

{2, 3, 4, 5, 6, 7, 8, 9 }

Returns: "111...111(27 digits)"

Statistics

Problem Statement for "MultiplesWithLimit"

Problem Statement

Definition

Constraints

Examples