algorithm - "Zero-One"多重编码如何解决？

Question

给定一个数 N，找到最小的“零一”数 S，它是 N 的倍数。“零一”数由数字 0 和/或 1 组成。

例如如果N=4然后 S=100这里100是 4 的最小整数倍其表示仅包含 0和/或 1数字。

我试过用蛮力的方式来做，但我正在寻找一种有效的解决方案。

Answer 1

您需要搜索要将 N 乘以的最小数字。

我会从最低有效数字开始逐步构建数字。

假设 N=7。乘数的可能最低有效数字是多少？这将是一个数字，当您乘以 7 时，结果的最低有效位为 0 或 1。如果您尝试 0-9 的数字，它只能是“0”或“3”。

+-------+--------+------+| Digit | Result | Pass |+-------+--------+------+| 0     |  0     | Yes  || 1     |  7     | No   || 2     | 14     | No   || 3     | 21     | Yes  || 4     | 28     | No   || 5     | 35     | No   || 6     | 42     | No   || 7     | 49     | No   || 8     | 56     | No   || 9     | 63     | No   |*-------*--------*------*

然后你尝试第二个最低有效数字。您现在将尝试 00、10、20、30、40、50、60、70、80、90 和 03、13、23、43、53、63、73、83、93。成功的候选人将是那些乘以 7 产生一个数字，其中两个最低有效数字为 0 或 1。你剩下“43”、“30”、“00”和“01”。

对第 3 位数字重复此过程，找到产生倍数的数字，其中 3 位最低有效数字符合要求。

在此过程中，您会找到一个所有数字都符合条件的数字，这就是您的答案。在 N=7 的情况下，您已经找到了第 3 位数字。 (7 * 143 == 1001)。