在線面試算法題-分糖果

作者丨安琪拉

來源丨安琪拉的博客

初一看題目，覺得好像很簡單，后來想了還是有點東西。

這個題目的關(guān)鍵點在前一個人拿完糖，剩下的糖果數(shù)量一定是4的整數(shù)倍。

我們來看第一個人和第二個人，第一個人把糖果分成5份，還多一個，他拿走其中的一份加多出的一個，剩下4份給第二個人，剩余糖果是不是4的整數(shù)倍。

那我們就反著推導(dǎo)，假如最后一個人，也就是到第五個人，糖果剩余假設(shè)為T5，T5 = 5n+1個，滿足題目要求，他可以拿n+1個糖果。（平均分成5份，多一個，那其中一份和多出的一個）。

根據(jù)前面的結(jié)論，我們知道 5n +1 一定是4的整數(shù)倍，如果不滿足一定不符合題目要求：前一個人剩下4份糖果給后面的人。

第四個人準備拿時剩余糖果數(shù)假設(shè)為T4， T4 =  (5n+1) / 4 * 5 + 1  這個是關(guān)鍵，就是(5n+1) / 4 代表求出一份糖果的數(shù)量，* 5 + 1就是糖果總數(shù)。

遞推公式出來了，剩下就是寫代碼了，如下所示：

public class Candy {

    public static void main(String[] args) {
        //初始值為n 從最小的開始，因為滿足最小糖果
        int n = 0;
        int result;
        while((result = calculateCandyNum(n)) == -1) {
            n++;
        }
        System.out.println(result);
    }

    //當前值
    private static int calculateCandyNum(int n ) {
        int currentSum = 5 * n + 1;
        int executeNum = 5 -1;
        for (int i = 0; i < executeNum; i++) {
            // 一定要被4整除
            if (currentSum % 4 != 0) {
                return -1;
            }
            currentSum = currentSum / 4 * 5 + 1;
        }
        return currentSum;
    }
}

結(jié)果：

3121