Minimum Number of Days to Eat N Oranges LeetCode solution in C++

1
class Solution {
2
 public:
3
  // approach: BFS
4
  int minDays(int n) {
5
    int cnt = 0;
6
    queue<int> q;
7
    q.push(n);
8
    unordered_set<int> s;
9
    s.insert(n);
10
    while (!q.empty()) {
11
      int l = q.size();
12
      while (l--) {
13
        int a = q.front();
14
        q.pop();
15
        if (a == 0) break;
16
        if (s.find(a - 1) == s.end()) {
17
          q.push(a - 1);
18
          s.insert(a - 1);
19
        }
20
        if (!(a & 1) && s.find(a >> 1) == s.end()) { // if divisible by 2 and a/2 not present in set
21
          q.push(a >> 1);
22
          s.insert(a >> 1);
23
        }
24
        if (a % 3 == 0 &&
25
            s.find(a / 3) == s.end()) { // if divisible by 3 and a/3 not present in set
26
          q.push(a / 3);
27
          s.insert(a / 3);
28
        }
29
      }
30
      cnt++;
31
      if (s.find(0) != s.end()) break;
32
    }
33
    return cnt;
34
  }
35
};