如何查找重複數字在一個範圍內的數字

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個值。

不知道你想用哪種語言來解決，但大多數語言都支持循環和數組我想。