查找數量爲N，加起來10

Question

23雙位數的數目沒有對自2 + 3！= 10

73具有1對自7 + 3 = 10

783436具有3對自7 + 3,7 + 3,6 + 4 = 10

我試圖用遞歸來解決這個問題。這裏是我的基地情況：

if n < 10: 
     return 0 
    if n >= 10 and n <= 99: 
     if n % 10 + n // 10 == 10: 
      return 1 
     else: 
      return 0 

但遞歸步驟是躲避我。

Answer 1

這是一個奇妙的解決方案，如果你使用Python中的遞歸：下面的代碼

def ten_maker(some_number=str): 

    # Base case 
    if len(some_number) == 1: 
     return 

    # Comparing first item to the rest to see if it adds up to 10 
    for var in some_number[1:]: 
     if int(some_number[0]) + int(var) == 10: 
      print(some_number[0], var) 

    # Doing the same with the rest, and slowly finishing the string 
    return ten_maker(some_number[1:]) 

if __name__ == '__main__': 
    ten_maker("783436") 

Answer 2

如果你不在乎，你兩次計數7 + 3的事實（因爲3位數的序列中出現兩次），那麼你可以做如下（用Java編寫的）：

// a helper function that takes a number and returns an array of digits 
static int[] numberToDigits(int number){ 
    char[] charNums = String.valueOf(number).toCharArray(); 
    int[] digits = new int[charNums.length]; 
    for(int i=0; i<charNums.length; i++){ 
     digits[i] = charNums[i]-48; // convert the char to int value 
    } 
    return digits; 
} 

// here's the algorithm that counts the pairs 
static int count(int number){ 
    int[] digits = numberToDigits(number); 
    int counter = 0; 
    for(int i=0; i<digits.length; i++){ 
     for(int j=i+1; j<digits.length; j++){ 
      if(digits[i]+digits[j] == 10){ 
       counter += 1; 
      } 
     } 
    } 
    return counter; 
} 

public static void main(String...args){ 
    int tens = count(783436); 
    System.out.println("tens = " + tens); 
} 

輸出
幾十= 3

Answer 3

你會發現其中一個解決方案給出了一個爲O（n ）複雜搜索解決方案ñ。您實際上可以編寫一個運行於O（n）的算法。這是它是如何完成的：

（1）運行數字並計算所有的1，2，... 9's。

int[] A = new int[] {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; 
String numStr = "783436"; 
for(char c: numStr.toCharArray()) 
    A[c - '0'] += 1; 

（2）只有某些對添加到給你10，{1,9}，{2,8}，{3,7}，{4,6}，{5,5} 。使用該信息總結對：

int pairs = A[1]*A[9] + A[2]*A[8] + A[3]*A[7] + A[4]*A[6] + A[5]*A[5]; 

（注：你乘計數，因爲，在這個問題指出，對不必須是唯一的）

---

舉個例子採取783436（注：這是不實際的代碼，我只是想說明）：

//The counts for digits 1 - 9 
A = {0, 0, 2, 1, 0, 1, 1, 1, 0} 

pairs = 0*0 + 0*1 + 2*1 + 1*1 + 0*0 = 3 

Answer 4

這裏是我的解決方案沒有recrussion

code at online compiler

---

public static void main (String[] args) 
{ 
    // add user input 
    int SUM = 10; 
    // add user input 
    String numStr = "783436"; 

    int length = numStr.length(); 

    int numArray[] = new int[length]; 
    int numArrayNeed[] = new int[length]; 

    int temp=Integer.parseInt(numStr); 
    int i=0; 

    do 
    { 

     numArray[i] = temp % 10; 
     temp = temp /10; 

     numArrayNeed[i] = SUM - numArray[i]; 

     i++; 

    }while(temp>0); 

    for(int j=0;j<length;j++) 
    { 
     if(numStr.contains(String.valueOf(numArrayNeed[j]))) 
     { 
      System.out.println(": " + numArrayNeed[j] + " & " + (10-numArrayNeed[j])); 
     } 
    } 


} 

Answer 5

使用它的n階（最佳）。

以一個全局變量將舉行0-9

private int[] countOfDigits = new int[10]; 

使用下面的方法將返回可用對的總數發生。

int countPair(int num) { 
    while (num > 0) { 
     countOfDigits[num % 10]++; 
     num /= 10; 
    } 

    return ((countOfDigits[1] * countOfDigits[9]) 
      + (countOfDigits[2] * countOfDigits[8]) 
      + (countOfDigits[3] * countOfDigits[7]) 
      + (countOfDigits[4] * countOfDigits[6]) + (countOfDigits[5] 
     * (countOfDigits[5] - 1)/2)); 
    }