Задание:
Given is array containing N numbers, A[0], A[1], ... A[N-1]. Compute the array B of length N, such that B[i] = A[0]*A[1]*...A[i-1]*A[i+1]...*A[N-1]. Algorithm should work in time O(N), memory O(1) and can't use division.
Решение 1:Given is array containing N numbers, A[0], A[1], ... A[N-1]. Compute the array B of length N, such that B[i] = A[0]*A[1]*...A[i-1]*A[i+1]...*A[N-1]. Algorithm should work in time O(N), memory O(1) and can't use division.
Конечно тут не чисто O(N), так как за логарифмом и экспонентой вряд ли O(1).
Решение 2:
А тут чистенько все вроде. Даешь еще решения в комментах!
No comments:
Post a Comment