HugeGraph | Topcoder Archive

Problem Statement

Cat Snuke has drawn a huge graph. You are given a long n and a long[] d that describe the graph. The graph has n vertices, numbered 0 through n-1. Vertices i and j are connected by an edge if and only if |i-j| is an element of d. Return the number of connected components of this graph.

Definition

Class:: HugeGraph
Method:: countComponents
Parameters:: long, long[]
Returns:: long
Method signature:: long countComponents(long n, long[] d)
(be sure your method is public)

Constraints

n will be between 2 and 10^18, inclusive.
d will contain between 1 and 50 elements, inclusive.
Each element of d will be between 1 and n-1, inclusive.
Elements of d will be pairwise distinct.

Examples

```
5
```
```
{2}
```
```
Returns: 2
```
The graph will look as follows: There are two connected components in this graph: {0, 2, 4} and {1, 3}.
```
6
```
```
{2, 3}
```
```
Returns: 1
```
```
10
```
```
{6, 8, 9}
```
```
Returns: 3
```

{10, 20, 30, 40, 50, 60, 70, 80, 90}

Returns: 10

```
33
```
```
{30, 29, 26, 15}
```
```
Returns: 5
```
```
808
```
```
{195, 774, 788, 781, 723}
```
```
Returns: 71
```

47933736652472

{47932970752927, 47933439462262, 2570167893116, 47933306684356, 47931823444952}

Returns: 2566761627725

45466964736857613

{33250482667239488, 37822264384529608, 40095838646694298, 43479356281340667, 35203783529829951,
 40580747920061306, 43377164971019776, 39064579296221318, 40001593684678420, 33451277901601382,
 40995812050106167, 37014304154501058, 17759267713188789, 36704554868973353}

Returns: 3274732884432575

927386907126310589

{748147148561484840, 701393167746858761, 769696254000454180, 704972921953280463, 759946249333871738,
 884450289438010670, 746985782208205106, 774136608403627034, 340934288037171102, 842771692796482305,
 781200159564662404, 714890479593837724, 692135607544998078, 869198777483846839, 857427314409450650,
 769959320733418646, 834561823397164073, 859931184678488658, 772342405210344280, 884209280453229287,
 742707070877737742, 713634305824576668, 885018270712907537, 774793793947310152, 742703922481466469,
 903242244337866282, 891008000483677106, 811279910869615440, 741113236129095213, 739459726110363505,
 762358705144212813, 830373753788440496, 908779619221983459, 887664283422679667, 759617794878713552,
 910640611592949081, 783409949952075625, 863540471792847786, 927341859483997999, 836772868602095563,
 698935183681576178, 862350615052508395, 878270753526059153, 702073460709372995, 699733226194776258,
 695875778245571985, 827812810943605830, 873126653781760917, 889807390074772165, 897362441882835952}

Returns: 95415956985202718

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.