查找可写为1和0的数字的倍数

Question

给定数字n (2 <= n <= 1000)，找出其中最小的非零倍数，其以10为基数，只有数字0和1。示例:2个-> 10、3个-> 111、4个-> 100、7个-> 1001、11个-> 11、9个-> 111 111 111。

我的想法不是很好：{/* n|2 -> n|5 +“000”(最大幻觉(2，5))-> n|3 + "111“*/}

我认为，遵循剩余的数字除法由数字n组成，格式为0/1。谢谢您的帮助！

Answer 1

您可以使用breadth first search。首先查询1，因为您的数字必须以1开头，然后每次从队列中提取一个数字x时，查看它是否是n的倍数。如果是，您就得到了答案；如果不是，请按顺序在队列中插入x * 10和x * 10 + 1。

请注意，实际上不必将除法s和0s的整个字符串存储在队列中:存储除法的剩余部分和一些辅助信息就足够了，这些信息使您可以重新构造实际的字符串。如果你需要更多关于这方面的细节，请回信。

Answer 2

非暴力方法是遍历仅包含0和1的一系列数字，然后确定该数字是否为所讨论数字的倍数。这种方法比遍历n的倍数并确定它是否只包含0和1的效率要高得多。

IVlad's suggestion是生成序列(只包含0和1的数字)的更有效的方法。但是，如果您更喜欢动态生成数字(队列没有内存开销)，则可以简单地迭代整数(或使用循环索引)，并将每个值的二进制表示解释为十进制数。

2 (Decimal) ->  10 (Binary) -> (interpret as decimal 10)
3 (Decimal) ->  11 (Binary) -> (interpret as decimal 11)
4 (Decimal) -> 100 (Binary) -> (interpret as decimal 100)
5 (Decimal) -> 101 (Binary) -> (interpret as decimal 101)
... and so on.

对于转换，我怀疑可以通过链接对Integer.toBinaryString()和String.parseInt()的调用来完成，但很可能有更有效的方法来实现。

这里有一个在线演示，可以帮助您入门：http://jsfiddle.net/6j5De/4/

Answer 3

public static int result(int num)
{
    int i =2;
    while(true)
    {
        int mult = Integer.parseInt(Integer.toString(i++,2));
        if( mult % num == 0) //Check whether it is a multipler of given number or not ?
        {
            return mult;
        }
    }
}