如何查找重复数字在一个范围内的数字

Question

我在查找范围为000000000..999999999的所有数字，其中至少有3个或更多相似的数字组合在一起。

以下是通过整数的例子：111234567112333678，122111876

下面是失败的整数的例子：122334455123456789，123123123

我跑在Ruby中这行，然后我的MacBook Pro具有16 GB的RAM跑出的存储器：(000000000..999999999).to_a.select{|e| e.to_s =~ /(\d)\1+/}

Answer 1

递归溶液：

• 生成从000到999的所有数字，并使用n % 111来检查 每个数字是否为111的倍数。如果是，请将标志设置为true。
• 对这些数字中的每一个，添加一个数字，范围为0-9，如果数字的标志为假，则使用​​检查最后三位数字是否相等，如果是，则将该标志设置为true。
• 以递归方式重复上一步，直至达到7位数。
• 然后，对于每个7位数的数字，如果其标志为真，则将00-99的完整范围作为最后两位数字（生成一百个9位数 数字）。
• 如果该标志为假，则使用(n % 100) % 11检查是否最后 两个数字是相等的，并且如果是这样，添加第三个相等数字和 然后最后一位范围内的0-9（产生10 9位数 数字）。
• 如果最后两位数字不相等，则添加两位数字，等于 最后一位数字（生成一个9位数字）。

---

这里有一个简单的JavaScript实现。只计算结果很快，但如果打开打印，则对于超过6位的数字，只需几分钟而不是几秒。

function repeatingDigits(len) { 
 
    for (var n = 0; n < 1000; n++) { 
 
     var flag = n % 111 ? false: true; 
 
     add_digit(10 * n, flag, len - 3); 
 
    } 
 
} 
 
function add_digit(n, flag, len) { 
 
    for (var d = 0; d < 10; n++, d++) { 
 
     var f = (!flag && (n % 1000) % 111 == 0) ? true : flag; 
 
     if (len > 3) add_digit(10 * n, f, len - 1) 
 
     else add_final(100 * n, f); 
 
    } 
 
} 
 
function add_final(n, flag) { 
 
    if (flag) { 
 
     for (var d = 0; d < 100; n++, d++) { 
 
      ++count; // document.write(n + " "); 
 
     } 
 
    } 
 
    else if ((n % 10000) % 1100 == 0) { 
 
     n += (n % 1000)/10; 
 
     for (var d = 0; d < 10; n++, d++) { 
 
      ++count; // document.write(n + " "); 
 
     } 
 
    } 
 
    else { 
 
     n += ((n % 1000)/100) * 11; 
 
     ++count; // document.write(n + " "); 
 
    } 
 
} 
 

 
var count = 0; 
 
repeatingDigits(9); 
 
document.write(count);

有3个或多个数字重复组整数的个数是：

3 digits:    10 
4 digits:   190 
5 digits:   2,800 
6 digits:   36,910 
7 digits:  457,390 
8 digits:  5,448,700 
9 digits:  63,154,810 
10 digits: 717,431,590 
11 digits: 8,025,277,600 
12 digits: 88,684,382,710 

Answer 2

让我们看看有多少数字有三个或更多重复的数字你有。让我们关注“1”重复3次或更多次的组合。

要计算这个数字，我们需要考虑只有3个，仅有4个，......所有10个出现的“1”的字符串。

这是累积的binamial probabilty whcih可以计算如下：

cumulative = 0; 
for k = 3:10 
    cumulative = cumulative + (1/10)^k*(9/10)^(10-k)*nchoosek(10,k); 
end 
disp(cumulative) 

答案是0.0702。但总共有10 不同的数字。所以，只考虑重复“1”，你得到0。0702 * 10 数字。

---

关于您当前的实施。我对Ruby不太了解，但我假设to_a产生一个范围的数组，所以你要求创建数组的数组。假设每个数字需要8个字节（不能在4个字节中存储9,999,999,999），所以最终的结果是10^10 * 8/1024^3〜= 74.5 GB。

Answer 3

算来，采取所有9位数字，

999999999 + 1 

减去9位数的号码的数量不连续的相似的数字，

- 9^9 

并减去9位数字的号码与一个或多个组连续相似的两位数字，

- (10 - 2*k) choose k * 9^(9 - k) for k=1 to 4 

要列出他们lexicogr aphically，我们可以使用下面的方法：

Until done: 
    Increment the number until done or the next increment would invalidate it 
    If the third digit from the right is less than 9: 
    Increment it and set the last two to the same digit 
    Increment all three last digits at once until they are 999 
    Increment the first digit, l, left of the the third digit 
    from the right that is less than 9 
    Set the digits right of l to 0 

Answer 4

为什么不能在一个阵列中提取每一个数字，并检查是否任何数字已经连续出现3次？

int number = 666455477; 

int counter = 0; 
//l = number of digits 
int l = (int)(Math.Log10(number) + 1); 
int[] array = new int[l]; 

//Numbers get inserted in reverse order, but doesnt matter 
while (number > 0) 
{ 
    array[counter] = number % 10;  

    if(counter > 1) 
    { 
     if (array[counter] == array[counter - 1] && array[counter] == array[counter - 2]) 
      Console.WriteLine("Number contains 3 consecutive: {0}'s", array[counter]); 
    } 
    number /= 10; 
    counter++; 
} 

这样，您还可以将大数字作为字符串存储，读入每个字符并将其解析为int数组。如果你不想使用一个数组，你可以简单地有3个变量存储当前和前2个值。

不知道你想用哪种语言来解决，但大多数语言都支持循环和数组我想。