在线面试算法题-分糖果

作者丨安琪拉

来源丨安琪拉的博客

初一看题目，觉得好像很简单，后来想了还是有点东西。

这个题目的关键点在前一个人拿完糖，剩下的糖果数量一定是4的整数倍。

我们来看第一个人和第二个人，第一个人把糖果分成5份，还多一个，他拿走其中的一份加多出的一个，剩下4份给第二个人，剩余糖果是不是4的整数倍。

那我们就反着推导，假如最后一个人，也就是到第五个人，糖果剩余假设为T5，T5 = 5n+1个，满足题目要求，他可以拿n+1个糖果。（平均分成5份，多一个，那其中一份和多出的一个）。

根据前面的结论，我们知道 5n +1 一定是4的整数倍，如果不满足一定不符合题目要求：前一个人剩下4份糖果给后面的人。

第四个人准备拿时剩余糖果数假设为T4， T4 =  (5n+1) / 4 * 5 + 1  这个是关键，就是(5n+1) / 4 代表求出一份糖果的数量，* 5 + 1就是糖果总数。

递推公式出来了，剩下就是写代码了，如下所示：

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;
    }
}

结果：

3121