C++でN個のクラッカーをK人に分配したときの最大値と最小値の差の最小値を求める

この記事では、2つの整数 N と K が与えられたとき、N個のクラッカーをK人のユーザーに分配する問題を解説します。目標は、あるユーザーが受け取るクラッカーの最大数と、別のユーザーが受け取る最小数の差として考えられる最小値を求めることです。

問題の例

たとえば、入力が N = 7、K = 3 の場合を考えてみましょう。このとき出力は 1 になります。なぜなら、各ユーザーがそれぞれ 2個・2個・3個 のクラッカーを受け取るとき、最大数（3個）と最小数（2個）の差は 1 になるからです。

解法のアプローチ

この問題は非常にシンプルな論理で解くことができます。

• N が K で割り切れる場合：全員が同じ個数（N ÷ K 個）を受け取れるため、最大と最小の差は 0 になります。
• N が K で割り切れない場合：どう分配しても、一部のユーザーが他より1個多く受け取ることになり、差は最低でも 1 になります。

つまり、アルゴリズムは次のようにまとめられます。

if n mod k is same as 0, then:
    return 0
Otherwise
    return 1

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int solve(int n, int k){
    if (n % k == 0){
        return 0;
    } else{
        return 1;
    }
}
int main(){
    int N = 7;
    int K = 3;
    cout << solve(N, K) << endl;
}

入力

7, 3

出力

1

計算量について

この解法は剰余演算を1回行うだけで済むため、時間計算量は O(1)、空間計算量も O(1) となります。どれほど大きな N や K が与えられても、即座に答えを導き出せる効率的なアルゴリズムです。