Graph on array SnackDown1A

can anyone help ,how to solve this question asked in snackdown round 1A?
Graph on Array

It has a pretty straight forward Algorithm:

if( GRAPH IS CONNECTED )
then: No Modification NEEDED, Output 0 and the same array
else{
if( ALL of the numbers are not 47 )
then just make a[0]=47
else
then just make a[0]=43;
Output 1 and the the array
}

We made the first element 47 as that is the biggest prime number less than 50 and will itself be co-prime to all other numbers and will be connected to all of the other numbers hence making the graph connected. Here, we are just missing the case when all of the input numbers are already 47 like (47 47 47), in that case we can do the same thing with 43 and make it (43 47 47)

P.S. Don’t miss the case when N=1.

1 Like