I am seeking a data structure that maintains an array of N numbers and supports the following two operations:

  1. Double the first i numbers
  2. Subtract the first i numbers of a previous version from the current version.

It always starts with an array filled with 1s, and we only need to know the final array (after all operations have been applied). The algorithm doesn't have to be online. Assume overflow won't happen.

Is it possible to solve this in close to linear running time (e.g., Q log N or Q sqrt N where Q is the number of operations)? I invented this problem for a programming contest and I'm wondering how efficiently this can be done.

Here is an example:

We start with the array [1,1,1,1] (version 1)

Double the first 3 numbers to get [2,2,2,1] (version 2)

Double the first 1 numbers to get [4,2,2,1] (version 3)

Subtract the first 3 numbers of version 1 to get [3,1,1,1] (version 4)

Subtract the first 1 numbers of version 2 to get [2,1,1,1] (version 5)

Then the program would output the final version: [2,1,1,1]

  • 1
    $\begingroup$ Welcome to CS.SE! Interesting design challenge. Can you share the context where you encountered this problem? I am curious about the motivation. $\endgroup$ – D.W. Jun 27 '18 at 21:14
  • $\begingroup$ @D.W. actually this was part of a problem I thought of for a competitive programming challenge. The original problem was to count the number of paths in a interval graph with updates, which (hopefully) simplifies down to this problem. $\endgroup$ – sunny-lan Jun 27 '18 at 21:15
  • $\begingroup$ Cool. So you invented this problem? Do you have any reason to think there is an algorithm whose running time is close to linear? $\endgroup$ – D.W. Jun 27 '18 at 21:17
  • $\begingroup$ @D.W. not really :), just for fun. The non-linear solution is considered 'too easy' by some people, forcing it to be linear will make it a lot harder (may be impossible though!) $\endgroup$ – sunny-lan Jun 27 '18 at 21:21
  • $\begingroup$ OUTPUT of N numbers on its own is O(N) that is larger than sqrt(N) or Q*sqrt(N) for any fixed Q $\endgroup$ – Bulat Jun 27 '18 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.