C中的算法 - 用数字进行数字 - 单位为3的数字

Question

我在接受采访时遇到了这个问题.任何单位位置为3的数字至少有一个包含所有1的数字.例如,3的倍数是111,13的倍数是111111.给定一个以3结尾的数字,我被问到找到包含全1的多重的最佳方法.现在可以采用一种直接的方法,在这种方法中你不考虑空间问题,但随着数量的增加,有时候即使它没有,C中的int(或者那个长的int!)也不能保持那个倍数.在C中实现这种算法的最佳方法是什么？

Answer 1

更新:纳入Ante的观察并制作答案社区维基.

像往常一样在这类问题中,编码任何工作强力算法都比较容易,但算法越多.你使用铅笔和纸,你可以获得更好(更快)的算法.

让我们使用简写符号:让M(i)表示1111 ... 1(i).

给定数n(假设n = 23),您希望找到一个数m,使得M(m)可被n整除.一个简单的方法是检查1,11,111,1111 ......直到我们找到一个可被n整除的数字.注意:可能存在用于查找给定n 的闭合形式的解决方案,因此该方法不一定是最优的.

当迭代M(1),M(2),M(3),......时,有趣的部分显然是如何检查给定数字是否可被n整除.你可以实现长除法,但任意精度算术很慢.相反,请考虑以下事项:

假设您已经从之前的迭代中知道了M(i) mod n.的值.如果M(i) mod n = 0,那么你已经完成了(M(i)是答案),所以让我们假设它不是.你想找到M(i+1) mod n.因为M(i+1) = 10 * M(i) + 1,你可以很容易地计算M(i+1) mod n出来(10 * (M(i) mod n) + 1) mod n.即使对于较大的n值,也可以使用固定精度算法计算.

这是一个函数,它计算可被n整除的最小数量(从Ante的Python答案转换为C):

int ones(int n) {
        int i, m = 1;
        /* Loop invariant: m = M(i) mod n, assuming n > 1 */
        for (i = 1; i <= n; i++) {
                if (m == 0)
                        return i;  /* Solution found */
                m = (10*m + 1) % n;
        }
        return -1;  /* No solution */
}