Skip to content

Instantly share code, notes, and snippets.

@KeyC0de
Created November 21, 2020 12:16
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save KeyC0de/a846d9bedc8220059fe996aacf6a84df to your computer and use it in GitHub Desktop.
Save KeyC0de/a846d9bedc8220059fe996aacf6a84df to your computer and use it in GitHub Desktop.
#include <stdio.h>
#include <stdlib.h>
#include "circularLinkedList.h"
// solve the Josephus problem
int josephusSolve(int N, int M)
{
// Create a List with N soldiers
Node* L = createCircularLList(N);
Node* dead = NULL; // to free the dead soldier Node
//printList(L, N); // check everything's allright
Node* target = (Node*) malloc(sizeof(Node));
target->id = 0;
target->next = L; // pointer to start of the LList
// Eliminate an M-th Node with each iteration and continue as long as at least one Node remains
// In other words, we skip M-1 Nodes and eliminate the M-th Node
int i, count = N;
while (count) {
for (i = 1; i < M; ++i)
target = target->next;
// now reached (currentNode + M - 1)th Node
dead = target->next;
target->next = target->next->next; // skip the Mth (next) Node (ie. eliminating it from the list)
free(dead); // free dead
count--;
}
return target->id;
}
// call like so:
int main(int argc, char **argv)
{
if (argc < 3) {
printf("Call function like so: ./josephus N M (substitude N with # of Nodes and M with the step)\n");
return -1;
}
int N = atoi(argv[1]); // Total # of soldiers
int M = atoi(argv[2]); // step
int winner = josephusSolve(N, M);
printf("\nGiven %d soldiers and skipping %d the last one standing will be @ position No%d.\n", N, M, winner);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment