Let the G be a graph with 100 vertices numbered 1 to 100 Two vertices i and j

Let the G be a graph with 100 vertices numbered 1 to 100
Two vertices i and j are adjecnt if | i-j| =8 or | i-j|
=12. The Number of connected components in G is ?

Question Posted / vivinn

4 Answers
14249 Views
I also Faced
E-Mail Answers

Answers were Sorted based on User's Feedback

Let the G be a graph with 100 vertices numbered 1 to 100 Two vertices i and j are adjecnt if | i-j..

Answer / rakesh

Is This Answer Correct ?

20 Yes

7 No

Let the G be a graph with 100 vertices numbered 1 to 100 Two vertices i and j are adjecnt if | i-j..

Answer / yogesh

as i-j=8 is connected that means
a) 1,9,17,25....are connected
b) 2,10,18.26... are connected
.
.
e) 5,13,19,27.. are connected
.
.

h) 8,16,24,32 .. are connected

|i-j| = 12 are connected
that means
t)1,13,25,27 are conncted
y)2,14,26,38 are connected
u)3,15,27,
i)4,16,28...

obv because of t, even a and e are connected.
so only four series left i.e. a,b,c,d
a and b can never be connected because of odd numbers can
never be connected to even numbers in both the series.
so only possibity left is whether a and u or b and i can
be connected .
lets see a and u
a start with 1 and increments by 8
u starts with 3 and inctements by 12
this can match somewhere only if
for any value of m and n following is true
3+12*m = 1+8*n => 1+6*m = 4*n which can never be true

hence maximum number of connecte elements is 4.

Is This Answer Correct ?

6 Yes

4 No

Let the G be a graph with 100 vertices numbered 1 to 100 Two vertices i and j are adjecnt if | i-j..

Answer / sam

how u get answer 4?

Is This Answer Correct ?

2 Yes

2 No

Let the G be a graph with 100 vertices numbered 1 to 100 Two vertices i and j are adjecnt if | i-j..

Answer / achintya singhal

good question
there are 4 connected components..
first contains vertices numbered 1, 5, 9,13,17,21,25,29....
second contains 2, 6, 10, 14, 18.......
third one contains 3, 7, 11, 15......
fourth contains 4, 8, 12, 16, 20.......

Is This Answer Correct ?

5 Yes

6 No

Post New Answer

More Data Structures Interview Questions

What do you mean by hash table?

0 Answers

Can you please explain the difference between array_name and &array_name?

0 Answers

Complete structure of hashmap, very detail description, along with the basic coding of the hashmap internal implementation.

0 Answers Expedia,

What is the space complexity of quicksort?