MathDB
Make my array fast!

Source: STEMS 2021 CS Cat A Q2

January 23, 2021
combinatorics

Problem Statement

Given is an array AA of 2n2n numbers, where nn is a positive integer. Give an algorithm to create an array prodprod of length 2n2n where prod = A×A[i+1]×⋯×A[i+n−1],prod \, = \, A \times A[i+1] \times \cdots \times A[i+n-1], (A[x]A[x] means A[x mod 2n]A[x \ \text{mod}\ 2n]) in O(n)O(n) time without using division. Assume that all binary arithmetic operations are O(1)O(1)
Back to ProblemsView on AoPS