我今天在一个开发人员工作的面试中遇到了以下情况,这是其中一个问题,也是我唯一没有回答的问题。
把这个数连起来N N次,然后计算出他在2017年之前的模数。
例如:对于N=5,数字将为55555,结果将为Mod(55555,2017)= 1096;对于N=10,数字将为101010101010101010,结果Mod(101010101010101010,2017)= 1197
现在我必须计算的数字是58184241583791680。我得到的唯一提示是,58184241583791680的结果是58184241583791680乘以模数2017是一个4位数。
我在math.stackexchange上发布了this question,我得到了一个解决这个问题的数学方法,而不是蛮力。
我用JAVA写了下面的代码
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;
public class Puzzle {
final static BigInteger M = new BigInteger("2017");
public static void main(String [ ] args) {
for (long n : new long[] { 1L, 2L, 5L, 10L, 20L }) {
System.out.println(n + " --> " + bruteForce(n) + " --- " + formulaV2(n));
}
}
private static BigInteger bruteForce(long n) {
String s = "";
for (long i = 0; i < n; i++) {
s = s + n;
}
return new BigInteger(s.toString()).mod(M);
}
private static BigInteger formulaV2(long n) {
String aux = String.valueOf(n);
long L = aux.length();
long K = n;
double op1 = Math.pow(10,L*K);
BigDecimal minus1 = new BigDecimal(1);
BigDecimal p1 = new BigDecimal(op1).subtract(minus1);
double op2 = Math.pow(10,L);
BigDecimal p2 = new BigDecimal(op2).subtract(minus1).pow(-1,MathContext.DECIMAL64);
BigDecimal R = new BigDecimal(n).multiply(p1).multiply(p2);
R = R.setScale(0,BigDecimal.ROUND_UP);
BigInteger ret = R.toBigInteger();
return ret.mod(M);
}
}
我使用BigInteger和BigDecimal,因为我想得到真正大的数字(16位以上)的值。
bruteForce方法将简单地在循环中连接数字,而formulaV 2方法将使用数学论坛中提出的问题中的公式。
bruteForce方法只是用于验证。
然而,公式方法在N =10时工作良好<10 but no for N>。在N=10时,我得到了不正确的结果。
代码似乎与提供的公式一致(至少对我来说,也许我遗漏了一些东西),公式是正确的(我在Wolfram Alpha中检查过)。
我的猜测是,我有精度问题,也许BigDecimal在这种情况下不是合适的对象?.
6条答案
按热度按时间jucafojl1#
**使用数学!**一个好的面试官希望你用你的大脑和解决问题,而不是用蹩脚的代码来解决问题。
在这种情况下,他可能想让你用等式
1.(a + B)mod n = [(a mod n)+(b mod n)] mod n
以及例如将四位数连接三次与
xyzu * 100010001
相同,并且后者可以进一步分解为10000^0+10000^1+10000^2
。在你的例子中,基数x和重复次数y是一样的,而且都很大。但是模n很小。设D是x的下一个10次方。
因此,D mod n实际上不是D,而是小于2017。而不是计算D^y,你实际上可以计算((D mod n)^y)mod n,如果你在for循环中这样做,它最终(最多2017步后)cycle 或变为0。因此,您最多可以在2017次迭代中计算此项。所以这种聪明的方法的复杂度是O(n),其中n是模项,而朴素的方法需要O(x*y)内存。
有了这些技巧,你应该能够在不使用BigInteger的情况下完成这个任务,而且速度要快得多。
bbuxkriu2#
这是一个问题:
例如,当
n = 20
、L*K = 40
和op1 = 10000000000000000303786028427003666890752
时。至于为什么,通常的浮点业务:这是最接近的了不存在值正好为1E40的double
。op1
不会像这样打印(你会看到1E40,并认为一切都很好),但它会像这样转换。然后你将使用BigDecimal
,这很好(虽然有点奇怪),在此之前它已经出错了。我假设您使用了
BigDecimal
*,因为 * 您是从double
转换而来的,否则您将使用BigInteger
。只要使用BigInteger.pow
而不是Math.pow
,它可能会工作(它修复了这个问题,如果还有什么我没有注意到的,但我不能保证它会工作)。另一方面,
Math.pow(10,L)
不应该是一个问题,因为L
足够低。现在。你也可以改变它,让它在大的L
上工作。uelo1irk3#
double op1 = Math.pow(10,L*K)
这里对于n的大值将溢出。Double.MAX_VALUE 〜 1.710^308(即),对于LK > 308,它将溢出。
编辑:double将无法准确表示harold在回答中提到的小得多的值。
ct2axkht4#
我在https://stackoverflow.com/questions/38988665/java-puzzle-whats-the-correct-answer#comment 65349106_38988665上的评论中列出了这一切,但是你可以接受@Anony-Mousse和上面其他人所说的并使用它。
一个关键是提前找到10^17 mod 2017。Wolfram Alpha得到了正确的结果,无论如何是599,但在其他平台上,您可能需要将其视为((10^9 mod 2017)(10^8 mod 2017))mod 2017才能获得599。你还需要58184241583791680 mod 2017是2005(同样Wolfram也做对了,但是如果你不把它分解成(((581842415 mod 2017)(10^8 mod 2017)mod 2017)+83791680)mod 2017,那么较小的平台可能会出现问题。
因此,在(58184241583791680,但不要害怕)过程的每一步,你都在用你当前的数字乘以10^17(为了移动它以腾出空间进行串联),然后加上58184241583791680。但我们可以在2017年全部完成。在序列语言中,a sub 1 = 2005和a sub(n+1)=((a sub n)599+2005)mod 2017。这是for循环中的关键步骤。我在R中完成了前4040个左右的术语(喜欢你可以交互式地将它们放在屏幕上并仔细阅读它们-语言在我身上成长),尽管它真的足够做大约一半(工作中的好老鸽子洞原则)。它们不会循环,直到你真正到达2017年,也就是2005年。还有一艘潜艇4033号。
通常,a sub n = a sub(n mod 2016)。你想要一个子58184241583791680。58184241583791680 mod 2016是224说Wolfram Alpha [同样在较小的平台上,您可能需要将其分解为(((581842415 mod 2016)(10^8 mod 2016)mod 2016)+83791680)mod 2016],所以您需要一个子224。
如果人们想检查自己或我,我在R上得到的是465。但正如上面所指出的,过程才是问题真正感兴趣的。
llmtgqce5#
实际上,你可以在**log(n)**时间内完成。这比上面解释的任何方法都快。
你的工具箱里需要的东西:
1.power(a,B)with some modulo(如果模是素数,在你的情况下,它总是正确的)
1.在a%x + B%x ==(a+b)%x中乘法相似的知识。
1.求模逆
如果你不知道这些方法,你可以谷歌它。
现在到解决方案:
首先让你给定的num是1234,然后我们需要计算1234 1234 1234... 1234次
它等于1234 + 10^4 * 1234 + 10^8 * 1234 + 10^12 * 1234... 10^(4* 1233)* 1234
我们得到GP
==1234(10^(41234)- 1)/(10^4 - 1)**
用x替换1234,用y替换4(N中的位数)
我们得到x*(10^(x*y)-1)/(10 ^y- 1)
该幂函数和反函数仅花费log(n)时间
现在我们的答案是x (power(10,xy)-1)* inverse(power(10,y)-1);对所有这些取模就能得到答案
我可能犯了一些错误,请原谅。这可能是一个heafty读如果你不知道上述要求.
t40tm48m6#