array with a twist

Imagine that we have an array like structure A with n elements all of which are initially 0. ($A[i]=0$)

What is a data structure that supports the following operations:

1) Given an element A[i]=0 set A[i] to 1 in O(1) worst case

2) Given the index i return A[i] in O(1) worst case

3) Given the index i retrun the smallest $j\geq i$ such that $A[j]=0$ or $-1$ if there is no such index in amortized time as small as possible

Obviously an array supports the first 2. It doesnt not support 3). How to modify it?

• Can you only set entries from 0 to 1 or can you also set entries from x to 0? Dec 5 '13 at 2:03
• Only from 0 to 1 Dec 5 '13 at 4:00
• Yes, this is a nice homework exercise. What have you tried? What's the simplest technique you can think of to avoid repeating work? We expect you to make a serious effort on your own before asking here, and to show us what you've tried.
– D.W.
Dec 6 '13 at 1:08