We have a circular doubly linked list with several elements. Every element has a link to the next element, a link to the previous element and a boolean value (true or false). Four operations are defined for this list:
How to find the number of list elements with such conditions? Is it possible?
The idea was to cast all elements to the same value, except one. Counting elements amount of such a list is not a problem, but how can I find out, that all elements are traversed?
You can do this in O(N) time:
N=1
set current value = true
while(current value is true) {
N = N*2
set the next N values = false
go back N elements to get back to the starting element
}
// Now we know that the whole list is false
set current value = true
scan forward until you get to true again, while counting