Быстрый способ найти все числа X, которые суммируют себя с одной удаленной цифрой, чтобы получить N?

Question

Я работаю над заданием, которое дает целое число N и поручает нам найти все возможные комбинации X, Y, чтобы X + Y = N и Y = X с удалением одной цифры. Например, 302 будет иметь следующие решения:

251 + 51 = 302

275 + 27 = 302

276 + 26 = 302

281+ 21 = 302

301 + 01 = 302

Мой код для выполнения этого может найти все правильные ответы, но он работает слишком медленно для очень больших чисел (это занимает примерно 8 секунд длянаибольшее возможное число, 10 ^ 9, когда я хотел бы, чтобы весь алгоритм (до 100 из этих случаев завершился менее чем за 3 секунды).

Вот код, описывающий мое текущее решение:

//Only need to consider cases where x > y.
for(int x = n * 0.5; x <= n; x++)
{
     //Only considers cases where y's rightmost digit could align with x.
     int y = n - x,
         y_rightmost = y % 10;
     if(y_rightmost == x % 10 || y_rightmost == (x % 100) / 10)
     {
         //Determines the number of digits in x and y without division. places[] = {1, 10, 100, 1000, ... 1000000000}
         int x_numDigits = 0,
             y_numDigits = 0;
         while(x >= places[x_numDigits])
         {
             if(y >= places[x_numDigits])
                 y_numDigits++;

             x_numDigits++;
         }

         //y must have less digits than x to be a possible solution.      
         if(y_numDigits < x_numDigits)
         {
             if(func(x, y))
             {
                 //x and y are a solution.
             }
         }
}

Где func - это функция, определяющая, имеют ли x и y только однозначное различие. Вот мой текущий метод вычисления этого:

bool func(int x, int y)
{
    int diff = 0;
    while(y > 0)
    {
        if(x % 10 != y % 10)
        {
            //If the rightmost digits do not match, move x to the left once and check again.
            x /= 10;
            diff++;
            if(diff > 1)
                return false;
        }
        else
        {
            //If they matched, both move to the next digit.
            x /= 10;
            y /= 10;
        }
    }

    //If the last digit in x is the only difference or x is composed of 0's led by 1 number, then x, y is a solution.
    if((x < 10 && diff == 0) || (x % 10 == 0))
        return true;
    else
        return false;
}

Это самое быстрое решение, которое мне удалось найти до сих пор (другие методы, которые я пробовал, включали преобразование X и Y в строки и использование пользовательской функции подпоследовательности). вместе с разделением X на префикс и суффикс без каждой цифры справа налево и проверкой, суммировались ли какие-либо из них в Y, но ни одна из них не работала так быстро). Тем не менее, он все еще не масштабируется так, как мне нужно, с большими числами, и я изо всех сил пытаюсь придумать какие-либо другие способы оптимизации кода или основополагающих математических рассуждений. Любой совет будет принята с благодарностью.

Answer 1

Сначала попробуйте найти более простое решение:

• Найти X и Y так, чтобы X + Y = N

В псевдокоде ваши шаги должны выглядеть следующим образом:

• перебирает массив и с каждым данным item делает следующее:

  • добавляет это число в Set и проверяет, есть лиN - item

Это будет работать как сложность O (n) для уникального массива.

Так что улучшите его для работы с дублированныминумерует, сначала просматривая массив и добавляя счетчик дубликатов для каждого числа. Используйте какой-нибудь словарь для c ++ или расширьте Set. И каждый раз, когда вы найдете нужный номер, проверьте счетчик.

После этого вам просто нужно написать эту функцию «проверки цифр» и применить ее при поиске значения в Set.