leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1387.cpp (741B)

      1 class Solution {
      2     static inline constexpr const array<int, 1001> dp = []() constexpr -> array<int, 1001> {
      3         array<int, 1001> dp;
      4         dp[0] = 0;
      5         for (int i = 1; i <= 1000; i++) {
      6             int res = 0, n = i;
      7             while (n != 1) {
      8                 n = (n % 2) ? 3 * n + 1 : n / 2;
      9                 res++;
     10             }
     11             dp[i] = res;
     12         }
     13         return dp;
     14     }();
     15 
     16   public:
     17     int getKth(int lo, int hi, int k) {
     18         vector<int> vec(hi - lo + 1);
     19 
     20         iota(begin(vec), end(vec), lo);
     21         nth_element(begin(vec), begin(vec) + k - 1, end(vec),
     22                     [](const int a, const int b) { return dp[a] == dp[b] ? a < b : dp[a] < dp[b]; });
     23 
     24         return vec[k - 1];
     25     }
     26 };