N1 + N2 = N, N1 and N2 has only one digit difference. Given n, find all n1, n2 combinations


  • 0
    X

    suppose we have n1, n2. n2 is n1 without one digit
    e.g. n1 = 123, then n2 can be 12, 13 or 23.

    Now given N = n1 + n2, output all the possible combinations.


  • 0
    H
    This post is deleted!

  • 0
    H

    '''
    int n=30;
    int n1,n2;
    for(int i=0;i<n/2;i++)
    {
    int num=0;
    n2=i;
    String n2_string=String.valueOf(n2);
    n1=n-n2;
    String n1_string=String.valueOf(n1);
    for(int j=0;j<n2_string.length();j++)
    {
    char n2_single=n2_string.charAt(j);
    for(int k=0;k<n1_string.length();k++)
    {
    char n1_single=n1_string.charAt(k);
    if(n2_single==n1_single)
    {
    num++;
    }
    }
    }
    if(num==1)
    {
    System.out.println(n1+" "+n2);
    }
    }
    '''


  • 3

    Call the numbers A and B. B is A with one digit missing.
    We can write:
    A = 10^(k+1) X + 10^k Z + Y
    B = 10^k X + Y
    where Y < 10^k, Z < 10.

    Now look at N % 10.

    • If it is odd, and k > 0, then N % 10 = (A+B) % 10 = 2Y contradiction. Hence, k = 0, and A = 10X + Z, B = X. In the equation N = 11X + Z, we can try Z = N % 11, and if Z != 10 then there is the only solution X = (N - Z) / 11.
    • If it is even, then we know the last digit of Y up to two choices. For example, if N = 102, then Y%10 is either 1 or 6. If it is 1, then we want to solve the same problem for N = 10 and append 1 to the answers. If it is 6, then we want to solve the same problem for N = (102 - 12) / 10 = 9 and append 6 to the answer.
    def solve(N):
        if N == 0:
            return [(0, 0)]
        r = N % 10
        if r % 2:
            Z = N % 11
            if Z != 10:
                X = (N - Z) / 11
                return [(10 * X + Z, X)]
        else:
            choices = [x for x in xrange(10) if 2 * x % 10 == r]
            ans = []
            for choice in choices:
                N2 = (N - 2 * choice) / 10
                for A, B in solve(N2):
                    ans.append((10 * A + choice, 10 * B + choice))
            return ans
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.