Как сделать этот код даже быстрее?

Question

Следующий код предназначен для определения общего количества номеров между l и r, чей продукт цифр четный (для нескольких тестовых примеров t). Этот код работает отлично, но очень медленный для r больше, чем 100000. Может ли кто-нибудь предложить лучшую альтернативу?

#include <iostream> 
#include <algorithm> 
using namespace std; 
long long int nd(long long int x, int n) //return the digit at a particular index staring with zero as index for unit place 
{ 
while (n--) { 
    x /= 10; 
} 
return (x % 10); 
} 
int ng(long long int number) //returns total number of digits in an integer 
{ 
int digits = 0; 
if (number < 0) digits = 1; 
while (number) { 
    number /= 10; 
    digits++; 
} 
return digits; 
} 

int main() 
{ 
int t; 
cin>>t; 
long long int l[t], r[t], c; 
for(long long int j=0;j<t;j++) 
{ 
    cin>>l[j]>>r[j]; 
} 
for(long long int k=0;k<t;k++) 
{  
    long long int sum=0; 
    long long int t=0; 

    for(long long int i=l[k];i<=r[k];i++) 
    { 
    while(t<ng(i)) 
    { 
     c=nd(i,t); 
     if((c%2)==0) 
     { 
      ++sum; 
      break; 
     } 
     ++t; 
    } 
    t=0;  
    } 
cout<<sum<<endl; 
}  
cin.ignore(); 
cin.get(); 
return 0; 
}    

Answer 1

Все номера, начинающиеся с, например, 10 ..., 12 ..., 14 ..., ..., 2 ..., 30 ..., как известно, имеют четное произведение цифр. Поэтому я начинал с левой (более значимые цифры) и считал в блоках. Есть только несколько номеров, чей продукт цифр является нечетным (например, 1111111111), только здесь вы должны копать глубже.

Вот некоторые псевдокод:

int count(String prefix, int digits) { 
    int result = 0; 
    if (digits == 0) 
    return 0; 
    for (int d = 0; d < 10; d++) { 
    if (d%2 == 0) 
     result += 10**(digits-1); 
    else 
     result += count(prefix . toString(d), digits-1); 
    } 
    return result; 
} 

Это будет называться как count("2", 8), чтобы получить счетчик для интервала от 200000000 до 299999999.

---

Вот это реализация Haskell для целого блока (т.е. все d-номера):

blockcount :: Integer -> Integer 
blockcount 0 = 0 
blockcount d = 5 * 10^(d-1) + 5 * blockcount (d-1) 

., blockcount 1000 рассчитывается как 999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999906673638149678112100991045527618283038290855362829197537828566020403308902422436554555967290211889764040501006967575737578451247864596760515847918279606924376558933386167484972600492401409816848889950920373488688175948748520406620919482172887458489618930162114557351888053018577133904077798233708955720154383055111285253347199367163154735257073817013783479720680471050639288214933633125893456019446928186367940015517395804589878677037013049780548539009578539133163875520704796517313538234207308395257993406361095826210417788163492195444337155572607461248287214520321844365359628512231823310014460793073456057599128802632529825013737330925270323746419607 0623766166018953072125441394746303558349609375 гораздо меньше секунды.

Вам все равно придется добавлять код, который разбивает ваш диапазон на подходящие блоки.

Answer 2

Оптимизация на основе следующего будет работать:

Умножение двух чисел получает вы нечетность/ровности в соответствии с правилом

even * even = even 
odd * even = even * odd = even 
odd * odd = odd 

Поэтому вам нужно отслеживать только последнюю цифру номера ваших номеров.

Я слишком стар, чтобы закодировать это, но я держал пари, что это будет горячо быстро, как вам нужно только рассмотреть цифры от 0 до 9.

Answer 3

Я не могу понять, что делает ваш код, но основные принципов просты:

• value % 10 является младшим разрядом заказа
• value /= 10 удаляет цифре низкого порядка
• если цифра четная, то продукт будет даже.

Это должно привести к очень простому циклу для каждого значения. (Вы можете должны частный случай 0.)

Дальнейших оптимизации возможны: все четные номера будут иметь произведение цифр, даже, так что вы можете перемещаться с стадией 2, а затем добавить в количество эвенов (половина из диапазона) впоследствии. Это должно удвоить скорость.

Еще одна оптимизация: если цифра младшего разряда четна, само число является четным, поэтому вам не нужно извлекать младший разряд, чтобы проверить его.

Answer 4

Единственное, что вам нужно проверить, это если одна из цифр в номере четная. Если да, то он будет иметь 2 как фактор и, следовательно, быть четным.

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

Answer 5

Основная идея состоит в том, чтобы прокручивать каждую цифру числа и видеть, равномерна ли она. Если это так, весь продукт будет четным, и нет необходимости проверять оставшиеся цифры.

Проблема с вашим кодом заключается в том, что вы выполняете число через несколько раз, ища цифру с индексом i. Вы должны просто пробежать цифры числа после проверки равномерности по пути.

Вот сам за себя Go код, реализующий алгоритм:

package main 

func iseven(num int) bool { 
    for num > 0 { 
     digit := num % 10 
     if digit&1 == 0 { # same as digit%2 == 0, only simpler 
      return true 
     } 
     num /= 10 
    } 
    return false 
} 

func main() { 
    sum := 0 
    for n := 1; n < 1000000; n++ { 
     if iseven(n) { 
      sum++ 
     } 
    } 
    println(sum) 
} 

Производительность на моей машине:

λ time go run main.go 
980469 
go run main.go 0.05s user 0.01s system 81% cpu 0.073 total 

Update

Если вам нужно работать с Ginormous чисел, то можно использовать более эффективный подход.

Давайте позвоним по номерам, у которых произведение их разрядов нечетное номера додда. Таким образом, 135 является номером dodd, 134 нет. Аналогично, номера, которые имеют произведение своих цифр, даже называются deven. Таким образом, 134 - это номер.

Как уже упоминалось ранее, только цифры, состоящие из нечетных цифр, подвергаются обработке. Поэтому вместо перечисления чисел мы можем просто подсчитать числа, состоящие из цифр 1, 3, 5, 7 и 9. Для целого числа N > 1 имеются точно 10^N - 10^(N-1) номера, которые имеют N цифр. И из этих чисел, 5^N являются dodd, и поэтому 10^N - 10^(N-1) - 5^N являются deven.

Подход подсчитать, сколько Dodd числа есть в период между left и right границ, а затем вычесть этот подсчет из общего количества чисел между left и right. Вы могли бы также подсчитать только количество номеров, но это немного сложнее.

Эффективно, вы будете перебирать цифры с помощью этого подхода, а не через цифры. Мой implementation в Python способен вычислить количество дебютных номеров между 1 и int("1" * 100000) (число с цифр) за одну секунду.

Answer 6

Другая вещь, которую вы можете сделать, это изменить

while(t<ng(i)) 

в

int d = ng(i); 
while (t < d) 

Так нг вызывается только один раз в цикле.

Также нг только журнал (номер) +1 (логарифм 10), который

Я не знаю, что будет быстрее, хотя.

Answer 7

Во-первых, пожалуйста, исправить отступы

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

long long int nd(long long int x, int n) //return the digit at a particular index staring with zero as index for unit place 
{ 
    while (n--) { 
     x /= 10; 
    } 
    return (x % 10); 
} 

Это может быть исправлено легко с помощью табличного

long long int nd(long long int x, int n) //return the digit at a particular index staring with zero as index for unit place 
{ 
    long long int pow10[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 
          100000000, 1000000000, 10000000000, 100000000000, 
          1000000000000, 10000000000000, 100000000000000, 
          1000000000000000, 10000000000000000, 
          100000000000000000, 1000000000000000000}; 

    return ((x/pow10[n]) % 10); 
} 

Аналогично, функция ng для получения общего количества цифр в целых числах может быть изменена на быстрый log10, не нужно многократно делить и подсчитывать. Конечно, потребуется небольшое изменение для адаптации 64-битных номеров.

int ng(long long int number) //returns total number of digits in an integer 
{ 
    int digits = 0; 
    if (number < 0) digits = 1; 
    while (number) { 
     number /= 10; 
     digits++; 
    } 
    return digits; 
}