Shortest path from 1 to n Geeks solution

Shortest path from 1 to n Geeks solution

  July 18, 2017    

---

Problem:

 Consider a directed graph whose vertices are numbered from 1 to n. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. find the minimum number of edges in a path in G from vertex 1 to vertex n.

Idea is to check the number for n/3 if not then subtract 1 and so on.

code:


import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
 {
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
   int count=0;
   int n=ab.nextInt();
    while(true)
   {
       if(n==1)
       break;
       if(n%3!=0)
   {
       count++;
       n--;
   }
   else if(n!=1)
   {
       n/=3;
       count++;
   }
   }
   System.out.println(count);
}
}
}