寻找能用1和0组成的某个数的倍数

Question

给定数字n（2 <= n <= 1000），找到最小的非零倍数，其以仅包含数字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格式化的数字。 感谢您的帮助！

- user1011460

---

这是作业吗？如果是，请标记为作业。 - NPE

看起来你尝试发布一些代码，但它绝对不是Java。 - Brendan Long

你能否请改进一下你的问题，我不确定我理解你的想法，而且我绝对不知道最后一段应该是什么意思。 - Slartibartfast

这是你的问题吗？http://www.spoj.pl/problems/ONEZERO/ - Purav Shah

Answer 1

你可以使用广度优先搜索。从队列中开始入队1，因为你的数字必须以1开头，然后每次从队列中提取一个数字x，看它是否是n的倍数。如果是，则找到了答案；如果不是，则按照顺序将x * 10和x * 10 + 1插入队列。

请注意，实际上您不必在队列中存储整个1和0字符串：只需存储除以n的余数和一些辅助信息，即可重构实际字符串。如果需要更多详细信息，请回信。

- IVlad

Answer 2

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

- Black_Rider

Answer 3

非暴力方法是遍历只包含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/。

- Shawn Chin