时间戳

首页 > 解决方案 > 大二进制数

java - 大二进制数

问题描述

我正在尝试解决一个问题，对于它正在工作的基本场景，但是，我知道它不是最佳的并且有几个错误。

问题：给你一个数字 n。求前 n 个正整数的二进制表示串联形成的数字的十进制值。打印答案 10^9 + 7。

输出格式：以 10^9 + 7 为模打印答案

约束：1 <= n <= 10^9

Sample input: 3
Sample Output: 27
The binary representation of 1: 1
The binary representation of 2: 10
The binary representation of 3: 11
Concatenated string: 11011 -> Decimal representation is 27.

我的第一个疑问是：“模10 ^ 9 + 7”，我理解是字符数的限制，但我不知道如何解释。

问题的第二部分是解决方案：输入：20

Binary representation of 2 : 10.
Binary representation of 3 : 11
Binary representation of 4 : 100. 
Binary representation of 5 : 101
Binary representation of 6 : 110
Binary representation of 7 : 111
Binary representation of 8 : 1000
Binary representation of 9 : 1001
Binary representation of 10 : 1010
Binary representation of 11 : 1011
Binary representation of 12 : 1100
Binary representation of 13 : 1101
Binary representation of 14 : 1110
Binary representation of 15 : 1111
Binary representation of 16 : 10000
Binary representation of 17 : 10001
Binary representation of 18 : 10010
Binary representation of 19 : 10011
The binary representation of 20: 10100
Concatenated string: 11011100101110111100010011010101111001101111011111000010001100101001110100

您建议如何解决此类问题？

这是我当前的代码：

public long FindBigNum(long n) {
    System.out.println("");
    System.out.println("Input: " + n);
    StringBuilder binaryRepresentation = new StringBuilder();
    for(Long i = 1l; i <= n; i++){
        System.out.println("Binary representation of " + i + " : " + Long.toBinaryString(i));
        binaryRepresentation.append(Long.toBinaryString(i));
    }
    System.out.println("Concatenated string: " + binaryRepresentation.toString());
    //System.out.println("Binary representation: " + binaryRepresentation.toString());
    long longRepresentation = parseLong(binaryRepresentation.toString(), 2);
    //System.out.println("longRepresentation: " + l);
    return longRepresentation;   
}

public long parseLong(String s, int base){
    return new BigInteger(s, base).longValue();
}

标签： javabinary

解决方案

我的第一个疑问是：“模10 ^ 9 + 7”，我理解是字符数的限制，但我不知道如何解释。

这意味着在除以该值时得到余数。它是值1000000007（我假设插入符号是指数）。

这是我将如何处理这个问题。

  • 像以前一样生成连接的字符串。
  • 用于BigInteger从二进制转换为十进制，然后mod使用 BigIntegermod方法。

这最终将非常缓慢且效率不高。但是，它可以作为一种控制，让您研究最佳的执行方式。也许使用 StringBuilder 并为其预先分配存储空间。编写自己的 int 到二进制转换例程等。它甚至可能需要更多的数学解决方案（例如数论）而不是编程解决方案。

但是您可以将您的结果与 BigInteger 解决方案进行比较，以验证它是否有效。

推荐阅读