LeetCode 2020-11-06: Find Smallest Divisor Given a Threshold

LeetCode の daily problem に挑戦した記録です。

今日の問題は Find the Smallest Divisor Given a Threshold (medium)。

問題の概要

• 与えられた正の整数の配列について、それぞれの要素を同じ除数で切り上げ除算した結果を合計した値を求める
• この合計した値が閾値以下となる 最小の除数 を求める

考え方

• 問題がちょっとややこしいのだけど、これは数学的に解を求めることができたりするのかな… 🤔
• ちょっといい方法が思いつかないので、愚直に解を探索する方法を考えよう
• まずは解となる除数の探索空間を考えてみよう
  • 配列の中に含まれる最大の整数が解の上限 となるね
    • 配列の長さ＝閾値の場合に、配列中の最大の整数が解になる
  • 解の下限は、例えば配列中の整数をすべて足し合わせて閾値で割った数値 などが使えそう
• そういうわけで、探索空間が（除数の上限・下限）が定まったら後は一つずつ候補の除数を試してみて条件を満たすかどうかを判定すれば OK 👍
• まずは線形探索で実装してみたけど、これはどうも time limit exceeded になりそうな予感…
  • 最適解かどうか怪しいけど、二分探索 を試みてみよう
• 二分探索で実装し直して submit → accept 🌟
  • Runtime 6ms で Your runtime beats 97.30 % of java submissions. ということは、二分探索が最適解っぽかった
• あと 1ms 削れないかなーと思って、探索空間の下限をよりスマートに求める方法とかを試してみたが無理だった 😢
  • 所詮二分探索するので、ちょこっと下限を最適にしてもループ一回減らせるかどうか、といったところだしなあ…

コード

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int low = 1;
        int high = 0;
        for (int num : nums) {
            high = Math.max(high, num);
        }

        while (low < high) {
	    // 除算演算子や算術右ビットシフト演算子を使うと low + high のオーバーフローを解消できないので、
	    // 論理右ビットシフト演算子を使っているところに注意
            int divisor = (low + high) >>> 1;
            long sum = 0;
            for (int num : nums) {
                sum += (num + divisor - 1) / divisor;
            }

            if (sum > threshold) {
                low = divisor + 1;
            } else {
                high = divisor;
            }
        }

        return low;
    }
}