Provide me some hint

#1

please provide some hint on how to approach this problem.

#2

Consider this as a graph(lines as edges and points as nodes). We need to add edges, such that there is a Euler Path . Now, first find the number of odd degrees in all the connected component
If in a connected component
(odd_vertex denotes number of odd degree vertex in the connected components)

  1. no of odd degree <= 2, then do odd_vertex+=2 ( to connect it with other connected component)
  2. no of odd degree >2 then do odd_vertex+=no of odd degree

we are doing this in order to eliminate any vertex with odd degree ( by adding an edge to it) because of we have a vertex with odd degree we can’t draw the graph in a single stroke

we will have ans=max(count_cc-1,(odd_vertex-1)/2) (count_cc is the number of connected components in the graph)

In case of any doubt feel free to ask :slight_smile:
if you got the answer mark your doubt as resolved

#3

in your solution,it will provide different answer for the given test case.

#4

for 2 1 1 2 1 2 2 1 2 it will give 2 but here answer is given as 1.

#5

yeah !! thanks for pointing that out I have corrected the algo

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.