CODEWITHSUNDEEP
c++josephus
Lithanium
Lithanium

Reputation: 41

Find the last K survivors in Josephus Problem in O(N)

I want to find the last K (very small K, K < 5) survivors in the classic Josephus Problem. I understand how only the LAST survivor can be found efficiently in O(N), but how do I work backwards to find the last K survivors?

This is the code I'm using for the problem, found on cp-algorithms.

int josephus(int n, int k) {
    int res = 0;
    for (int i = 1; i <= n; ++i)
      res = (res + k) % i;
    return res + 1;
}

The code gives the position that would be removed. Is there a way to alter this to find the 2nd last, 3rd last and so on to be removed? I am aware finding the exact positions can be done in O(N log N), but if I only want to find the last K, can it be reduced to O(N)?

Upvotes: 0

Views: 172

Answers (1)

bitmask
bitmask

Reputation: 34626

You can just log all values that you have encountered, discarding values you encountered more than k steps ago:

std::vector<int> josephus(int n, int k) {
    int res = 0;
    std::vector<int> ring(k); // ring buffer of size k
    std::size_t r = 0;
    for (int i = 1; i <= n; ++i) {
      res = (res + k) % i;
      ring[r++ % k] = res; // log all values in a ring buffer
    }
    std::vector<int> lasts(k);
    for (std::size_t j = 0; j < k; ++j) {
      lasts[j] = ring[r++ % K] + 1; // extract them in order
    }
    return lasts;
}

Upvotes: 0

Related Questions