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


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


You can only choose one of the actions per day.

Given the integer n, return the minimum number of days to eat n oranges.

&nbsp;
Example 1:

Input: n = 10
Output: 4
Explanation: 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.


Example 2:

Input: n = 6
Output: 3
Explanation: 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.


&nbsp;
Constraints:


	1 &lt;= n &lt;= 2 * 109


from collections import deque
from math import log2, ceil
class Solution:
    def minDays(self, n: int) -> int:
        maxd = 2*ceil(log2(n))
        que = deque([(1,1)])
        seen = set()
        while que:
            v, d = que.popleft()
            seen.add(v)
            if v == n:
                return d
            for w in [v+1, 2*v, 3*v]:
                if w not in seen and d <= maxd and w <= n:
                    que.append((w,d+1))
class Solution {
    HashMap<Integer,Integer>map;
    public int minDays(int n) {
        map = new HashMap<>();
        map.put(0,0);
        map.put(1,1);
        return dp(n);
    }
    public int dp(int n){
        if(map.get(n)!=null)
            return map.get(n);
         int one = 1+(n%2)+dp(n/2);
         int two = 1+(n%3)+dp(n/3);
        map.put(n,Math.min(one,two));
        return map.get(n);
}
    }
        // int one = 1+(n%2)+cache(n/2);
        // int two = 1+(n%3)+cache(n/3);
class Solution {
public:
    // approach: BFS
    int minDays(int n) {
        int cnt=0;
        queue<int>q;
        q.push(n);
        unordered_set<int>s;
        s.insert(n);
        while(!q.empty()){
            int l=q.size();
            while(l--){
                int a=q.front();
                q.pop();
                if(a==0)
                    break;
                if(s.find(a-1)==s.end()){ 
                    q.push(a-1);
                    s.insert(a-1);
                }  
                if(!(a&1) && s.find(a>>1)==s.end()){   // if divisible by 2 and a/2 not present in set
                    q.push(a>>1);
                    s.insert(a>>1);
                }
                if(a%3==0 && s.find(a/3)==s.end()){  // if divisible by 3 and a/3 not present in set
                    q.push(a/3);
                    s.insert(a/3);
                }
            }
            cnt++;
            if(s.find(0)!=s.end())
                break;
        }
        return cnt;
    }
};
var minDays = function(n) {
    const queue = [ [n,0] ];
    const visited = new Set();
    
    while (queue.length > 0) {
        const [ orangesLeft, days ] = queue.shift();
        
        if (visited.has(orangesLeft)) continue;
        if (orangesLeft === 0) return days;
        
        visited.add(orangesLeft);
        queue.push([orangesLeft - 1, days + 1]);
        
        if (orangesLeft % 2 === 0) {
            queue.push([orangesLeft - orangesLeft / 2, days + 1]);
        }
        
        if (orangesLeft % 3 === 0) {
            queue.push([orangesLeft - 2 * (orangesLeft / 3), days + 1])
        }
    }
};
Minimum Number of Days to Eat N Oranges