algorithm - 以 3 结尾的数字至少有一个倍数全为一

Question

嗨，这是在 Adob​​e 面试中被问到的一个问题。

Numbers ending in 3 have at least one multiple having all ones. 
for eg., 3 and 13 have amultiples like 111 and 111111 respectively. Given such 
a no. , find the smallest such multiple of that number. The multiple can 
exceed the range of int, long. You cannot use any complex data structure.

你能给我一个有效的解决方案吗

Answer 1

现在得到答案:)

int count=1, rem=1; 
while(rem)
{
 rem= (rem*10+1)%n; count++;
} 
 while(count--){ cout<<"1";}

Answer 2

这是一种比尝试 1、11、111、111 更有效的尝试。这能得到回报吗？有没有比一次尝试一个更优雅的答案？

将数字 1, 11, 111, ... 写为 (10^k - 1) / 9，已知除法是精确的。给定一个 10x+3 形式的目标数，我们希望找到最小的 k 求解 (10^k - 1) / 9 = Y(10x + 3) 其中 Y 是一个整数。寻找 10^k = 1 mod 9(10x + 3) 的小解。这是http://en.wikipedia.org/wiki/Discrete_logarithm，除了算术 mod 9(10x + 3) 不一定形成一个组 - 但是http://en.wikipedia.org/wiki/Baby-step_giant- step算法仍应适用，并可用于搜索稳定增加的 k 范围，而不是一次搜索一个 k 的可能值。

Answer 3

#include <iostream>
using namespace std;

int main() {
    int t;
    cin>>t;
    while(t--){
        long long n;
        cin>>n;
        long long cur = 1;
        while(cur%n!=0){
            cur = cur*10+1;
        }
        cout<<cur<<endl;
    }
    return 0;
}

Answer 4

与输出大小无关的解决方案：

public String ones(int n)
 {
    int i, m = 1;
    String num="1";

     for (i = 1; i <= n; i++) {
              if (m == 0)
              return num;
             /* Solution found */
             num=num+"1";
            m = (10*m + 1) % n;
    }
    return null;  /* No solution */

}

Answer 5

如果您正在寻找 Java 解决方案，这里是

public static void main(String[] args) {

    int input = 13; // this can be any number ending with 3
    int minAllOnesNum = 1;
    int nextAllOnesNum= minAllOnesNum;  

    int numberof1s=1;
    int count = 0;
    while(true)
    {
        count++;

        if(nextAllOnesNum%input == 0 ) 
        {
            break;  
        }

        nextAllOnesNum = nextAllOnesNum*10 + 1;

        if(nextAllOnesNum>=input) {
            nextAllOnesNum%=input;
        }
        numberof1s++;
    }


    System.out.println("Number of iterations : " + count);

    for(int i=1; i<=numberof1s; i++) {
        System.out.print("1");
    }
}

Answer 6

如果您正在寻找 Java 解决方案，这里是

public static void main(String[] args) {

    int input = 55333;
    int minAllOnesNum = 1;
    int nextAllOnesNum= minAllOnesNum;  

    int numberof1s=1;
    int count = 0;
    while(true)
    {
        count++;

        if(nextAllOnesNum%input == 0 ) 
        {
            break;  
        }

        nextAllOnesNum = nextAllOnesNum*10 + 1;

        if(nextAllOnesNum>=input) {
            nextAllOnesNum%=input;
        }
        numberof1s++;
    }


    System.out.println("Number of Iterations: " + count);

    for(int i=1; i<=numberof1s; i++) {
        System.out.print("1");
    }
}