6 ms·
On the first glance the first problem seems quite impossible. For example, if n is power of two, then for each prime number < n there will be a cycle starting w
by throwaput 10y ago
On the first glance the first problem seems quite impossible.
For example, if n is power of two, then for each prime number < n there will be a cycle starting with that number. If n is not a power of two, I haven't yet seen any good explanation of cycles.
Any hints? We can't use a or b in any way?
- throwaput 10y agoEven for power of two it's not correct, forget my statement about cycles.
- throwaput 10y agoYet I have only one idea - that we can permute the elements somehow (in a O(1) reversible way like a Gray code) so that the cycles would form something computable in O(n) time and O(1) space
- davidtgoldblatt 10y agoI think you're on the right track (i.e. viewing it as a permutation, and looking at the cycle decomposition of that permutation). Try indexing from 0 instead of 1 if you're not. Then the cycle containing 1 will start with (1, 2, 4, 8, ...). What happens when it wraps around?