ChocolatesByNumbers Problem in Java

这是谷歌、亚马逊、TCS、Accenture 等顶级 IT 公司面试中经常遇到的一个问题。通过解决这个问题，人们希望考察应聘者的逻辑能力、批判性思维和解决问题的能力。因此，在本节中，我们将用不同的方法和逻辑来解决 ChocolatesByNumbers 问题。我们还将为此创建 Java 程序。

ChocolatesByNumbers 是一个典型的基于编码的算法问题，侧重于计算在圆形排列中可以消耗的巧克力的实际数量。

巧克力排列成一行并放置在一个圆圈中，它们的索引号从 0 到 N-1。从吃零号巧克力开始，然后每隔 M 块巧克力吃一块，直到遇到一块已经被吃过的巧克力。

问题陈述

给定两个整数 N 和 M，其中：给定两个 整数 N 和 M，其中

N 在这里代表可想象的巧克力总数。

M 是你需要跳到的下一个巧克力的数量，并且是增量的。

信息收集的目的是确定一个人在再次遇到之前吃掉的巧克力的数量。

问题解决方案

要解决这个问题，必须找到 N 和 M 的可除性以及 N 和 M 的最大公约数。你可以吃的巧克力数量是 N/GCD(N, M)。

解释

步长和循环移动：如前所述，当步长是 M 的倍数时，在重新遇到之前吃过的巧克力之前完成的循环次数 = GCD (N, M)，因为这个 GCD 是可以被 N 和 M 整除的最大间隔。

吃掉的巧克力：在重复巧克力之前，一个人平均会消耗的巧克力数量将等于 N/ GCD(N, M)。

输出

 
Number of chocolates eaten: 5   

效率和性能

时间复杂度：由于在计算 GCD 时使用了 欧几里得算法，因此算法的时间复杂度为 O(log(min(N, M)))。

空间复杂度：空间复杂度为 O(1)；这是因为只需要常数级别的额外空间。

注意事项和边缘情况

在讨论给定的 ChocolatesByNumbers 问题时，了解 GCD 的广义概念如何应用于指定一个人所取巧克力的循环，这将很有趣。循环的长度由 N（总巧克力数）和 M（步长）的最大公约数给出。

互质值：在 N 和 M 互质（换句话说，它们的 GCD 为 1）的情况下，将以一种方式选择每块巧克力的精确一块，然后才再次选择任何一块。因此，请尽情享用您能吃到的所有 N 块巧克力。

M 为一：当 M 为一时，这意味着您从第一块巧克力开始，一块一块地前进。您也遍历了所有 N 块巧克力，因为步长意味着没有跳跃，并且所有巧克力都以所需的频率被取走。

大的 N 和 M：简单来说，这意味着当 N 和 M 的值很大时，计算 GCD 需要高效的计算。欧几里得算法确保此计算以相对于两个值中较小者的对数时间完成。

就算法的细节而言，N 非常小或 M 远大于 N 的变体对 GCD 查找周期长度没有影响。

结论

ChocolatesByNumbers 通过优化 N 和 M 的 GCD 来解决。因此，能够估计 N / GCD(N, M)，这代表了在重复之前可以消耗的不同巧克力的数量。它将识别步长和总巧克力的特定数学特征的挑战简化为保证效率。

因此，它在实践中可以快速解决任务，并且其时间和空间复杂度为 O(log(min(N, M)))，这使得它能够处理大数。学习通过巧克力步长形成的循环，可以为解决方案提供清晰直接的途径。