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 = 3 * i. The task is to find the minimum number of edges in a path in G from vertex 1 to vertex n.
Example 1:
Input:
N = 9
Output:
2
Explanation:
9 -> 3 -> 1, so
number of steps are 2. 
Ã¢â¬â¹Example 2:
Input:
N = 4
Output:
2
Explanation:
4 -> 3 -> 1, so
number of steps are 2.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minimumStep() which takes the N as inputs and returns the answer.
Expected Time Complexity: O(logN)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Graph algorithms

Data structures

Mathematics

Shortest paths

Starter code: #User function Template for python3



class Solution:

    def minStep (self, n):

        #complete the function here

Solutions:
class Solution:

	def minStep(self, n):
		c = 0
		while n != 1:
			if n % 3 == 0:
				n = n // 3
				c += 1
			elif n % 3 != 0:
				n = n - 1
				c += 1
		return c


class Solution:

	def minStep(self, n):
		cnt = 0
		while n != 1:
			if n % 3 == 0:
				n = n / 3
				cnt += 1
			else:
				n = n - 1
				cnt += 1
		return cnt


import math

class Solution:

	def minStep(self, n):
		if n == 1:
			return 0
		if n % 3 == 0:
			return 1 + self.minStep(n // 3)
		else:
			return 1 + self.minStep(n - 1)


from math import inf

class Solution:

	def minStep(self, n):
		return self.bfs(n, 0)

	def bfs(self, n, steps):
		if n == 1:
			return steps
		if n % 3 == 0:
			return self.bfs(n // 3, steps + 1)
		return self.bfs(n - 1, steps + 1)


class Solution:

	def minStep(self, n):
		count = 0
		curr = n
		while curr != 1:
			if curr % 3 != 0:
				curr -= 1
				count += 1
			else:
				curr /= 3
				count += 1
		return count


class Solution:

	def minStep(self, n):
		c = 0
		while n != 1:
			if n % 3 == 0 and n // 3 >= 1:
				n = n // 3
				c += 1
				continue
			else:
				n = n - 1
				c += 1
		return c


class Solution:

	def minStep(self, n):
		x = n
		v = set()
		q = []
		q.append(n)
		counter = 0
		while len(q) > 0:
			x = q[0]
			if x == 1:
				return counter
			q = q[1:]
			if not x in v:
				if int(x / 3) == 1 and x % 3 == 0 or x - 1 == 1:
					return counter + 1
				if x % 3 == 0:
					q.append(int(x / 3))
				else:
					q.append(int(x - 1))
				counter = counter + 1
		return counter


class Solution:

	def minStep(self, n):
		output = 0
		while n != 1:
			if not n % 3:
				n //= 3
			else:
				n -= 1
			output += 1
		return output


class Solution:

	def minStep(self, n):
		if n <= 1:
			return 0
		if n % 3 == 0:
			return 1 + self.minStep(n / 3)
		return 1 + self.minStep(n - 1)


class Solution:

	def minStep(self, n):
		ans = 0
		while n >= 2:
			if n % 3 == 0:
				n //= 3
			else:
				n -= 1
			ans += 1
		return ans


import math

class Solution:

	def minStep(self, n):
		i = n
		cnt = 0
		while i > 1:
			if i % 3 == 0:
				i = i / 3
				cnt += 1
			else:
				i -= 1
				cnt += 1
		return cnt


class Solution:

	def minStep(self, n):
		count = 0
		while n > 2:
			count += n % 3 + 1
			n = int(n / 3)
		if n == 2:
			count += 1
		return count


class Solution:

	def minStep(self, n):
		count = 0
		while n > 1:
			rem = n % 3
			count += rem
			n = n // 3
			if n == 1:
				count += 1
				break
			elif n < 3 and n > 1:
				count += n
				break
			else:
				count += 1
		return count


class Solution:

	def minStep(self, n):
		memo = {}

		def dp(i):
			if i in memo:
				return memo[i]
			if i == 1:
				return 0
			if i % 3 == 0:
				ans = 1 + dp(i // 3)
			else:
				ans = 1 + dp(i - 1)
			memo[i] = ans
			return ans
		return dp(n)


class Solution:

	def minStep(self, n):
		vis = 0
		curr = n
		while curr >= 1:
			if curr == 1:
				return vis
			if curr % 3 == 0 and curr / 3 >= 1:
				curr = curr / 3
				vis += 1
			else:
				curr -= 1
				vis += 1
		return -1


class Solution:

	def minStep(self, n):
		if n == 1:
			return 0
		elif n % 3 == 0:
			return 1 + self.minStep(n // 3)
		else:
			return 1 + self.minStep(n - 1)


class Solution:

	def graph(self, n, count):
		if n < 1:
			return count
		if n % 3 == 0:
			count += 1
			return self.graph(n // 3, count)
		elif n % 3 == 2:
			count += 1
			return self.graph(n - 1, count)
		else:
			count += 1
			return self.graph(n - 1, count)

	def minStep(self, n):
		count = 0
		k = self.graph(n, count) - 1
		return k


from collections import deque

class Solution:

	def minStep(self, n):
		ans = 0
		while n != 1 and n > 0:
			if n % 3 == 0:
				n = n / 3
				ans += 1
			else:
				n -= 1
				ans += 1
		return ans


import collections

class Solution:

	def minStep(self, n):
		steps = 0
		while n != 1:
			if n % 3 == 0:
				n /= 3
			else:
				n -= 1
			steps += 1
		return steps


class Solution:

	def minStep(self, n):
		c = 0
		i = 1
		while n > 1:
			if n % 3 == 0:
				n = n // 3
				c += 1
			else:
				n = n - 1
				c += 1
		return c