<p>There are <code>n</code> oranges in the kitchen and you decided to eat some of these oranges every day as follows:</p>

<ul>
	<li>Eat one orange.</li>
	<li>If the number of remaining oranges <code>n</code> is divisible by <code>2</code> then you can eat <code>n / 2</code> oranges.</li>
	<li>If the number of remaining oranges <code>n</code> is divisible by <code>3</code> then you can eat <code>2 * (n / 3)</code> oranges.</li>
</ul>

<p>You can only choose one of the actions per day.</p>

<p>Given the integer <code>n</code>, return <em>the minimum number of days to eat</em> <code>n</code> <em>oranges</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 10
<strong>Output:</strong> 4
<strong>Explanation:</strong> You have 10 oranges.
Day 1: Eat 1 orange,  10 - 1 = 9.  
Day 2: Eat 6 oranges, 9 - 2*(9/3) = 9 - 6 = 3. (Since 9 is divisible by 3)
Day 3: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1. 
Day 4: Eat the last orange  1 - 1  = 0.
You need at least 4 days to eat the 10 oranges.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 6
<strong>Output:</strong> 3
<strong>Explanation:</strong> You have 6 oranges.
Day 1: Eat 3 oranges, 6 - 6/2 = 6 - 3 = 3. (Since 6 is divisible by 2).
Day 2: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1. (Since 3 is divisible by 3)
Day 3: Eat the last orange  1 - 1  = 0.
You need at least 3 days to eat the 6 oranges.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 2 * 10<sup>9</sup></code></li>
</ul>

# Need a faster way of getting to the solution than bottom_up dp will top down be faster?
'''
5126970 -> -1
        -> %2
        -> %3
'''
# get to 0 fastest via BFS
class Solution:
    def minDays(self, n: int) -> int:

        myqueue = set()
        myqueue.add(n)
        steps = 0
        seen = set()

        while True:
            next_nums = set()
            while myqueue:
                curr_num = myqueue.pop()
                if curr_num == 0:
                    return steps
                seen.add(curr_num)
                option_1 = 1
                option_2 = curr_num//2 if curr_num%2 == 0 else 0
                option_3 = 2*(curr_num//3) if curr_num%3 == 0 else 0
                if curr_num - option_1 not in seen and curr_num - option_1 not in next_nums:
                    next_nums.add(curr_num-option_1)
                if curr_num - option_2 not in seen and curr_num - option_2 not in next_nums:
                    next_nums.add(curr_num-option_2)
                if curr_num - option_3 not in seen and curr_num - option_3 not in next_nums:
                    next_nums.add(curr_num-option_3)
            myqueue = next_nums
            steps+=1
                




#naive solution TLE
# class Solution:
#     def minDays(self, n: int) -> int:
#         dp = [math.inf for i in range(n+1)]
#         dp[0]=0
#         dp[1]=1

#         for num_oranges in range(2,n+1):
#             option_1 = 1
#             option_2 = num_oranges//2 if num_oranges%2 == 0 else 0
#             option_3 = 2*(num_oranges//3) if num_oranges%3 == 0 else 0

#             dp[num_oranges]=min(dp[num_oranges-option_1]+1,dp[num_oranges-option_2]+1,dp[num_oranges-option_3]+1)

#         return dp[-1]






# can eat 1 orange
# can eat n/2 oranges if %2 == 0
# can eat 2*(n/3) oranges if %3 ==0

# return min number of days to eat n oranges

# [0,1,2,3,4,5,6,...n]
# n is the minimum of number of oranges 1 away + 1
# numver of oranges n/2 away + 1
# number of oranges 2*(n/3) away + 1
# seems like dp problem

# 0 oranges require 0 days, 1 orange requires 1 day
# [0,1,]
# 2%2=0 -> (2/2)
# 2*(n/3) = 2*(3/3) -> can eat 2... dp[1] = 1+1 = 2
103