На тестировании решаю задачу. Есть массив чисел. Требуется получить сумму всех возможный array[i]*array[j] таким образом что array[i]*array[j] является сложением строк чисел и переводом их обратов число. Например.
array = [10,1]
10 * 10 => 1010
10 * 1 = 101
1 * 10 = 110
1 * 1 = 11
1010 + 101 + 110 + 11 = 1232
Писал 2 варианта решения с переводом в текст, сложением и обратно в число.
И с использованием first*(10**Math.log10(second))*10 + second.
В обоих случая не хватает времени для прохождение скрытых тестов. Как можно решит эту задачу?
Итак решение задачи за Линейное время O(3n) == O(n).
На примере массива: [20, 3, 400].
Ответом для задачи будет сложение 3х строк.
- а) 20 * (20,3,400)
- b) 3 * (20, 3, 400)
- c) 400 * (20, 3, 400)
Если расписать:
а) (20*100+20) + (20*10 + 3) + (20*1000 + 400) = 20 * (100+10+1000) + (20+3+400) = 20 * lgs + sum;
b) (3*100+20) + (3*10+3) + (3*1000+400) = 3*(100+10+1000) + (20 + 3 + 400) = 3 * lgs + sum;
c) (400*100+ 20) + (400*10+3) + (400*1000+400) = 4 * (100+10+1000) + (20+3+400) = 4 * lgs + sum;
Первый проход: Рассчитывается sum сумма элементов массива.
Второй проход: Рассчитывается lgs сумма 10 в степени логарифма десяти +1 от элемента: 10**(Math.log10(x)+1).
Третий проход: Рассчитывается сумма элемент умноженный на lgs плюс сумма.
Задача решена.
