I am trying to implement the Josephus election problem using an array as a mock circular linkedlist.
The item and next arrays represent nodes for circular linked list. On every Mth element one element is marked for removal. The next array skips over the marked index.
When there is one element left in the array we print out the element and the item that is left.
The problem is from Sedgewick C++ Algorithms books Chapter Third Edition. exercise 3.31.
The output I am getting is incorrect, I am not lost.
void array_represent_linked_list(int num_ints, int M) {
int* item = new int[num_ints];
int* next = new int[num_ints];
//populated item and next array with elements
for (int index = 0; index < num_ints; index++) {
item[index] = index + 1;
if (index == (num_ints - 1)) {
next[index] = 0;
}
else {
next[index] = index + 1;
}
}
int nums_left = num_ints;
int x = 0;
int count = 0;
int last_element_index = 0;
while ( nums_left > 1) {
//if current value divisible by M-2?
if ((count % M-2) == 0) {
if ((nums_left - 1) == 1) {
//record the next index which is the last element
last_element_index = next[x];
}
else {
//mark for removal of element from array
next[x] = next[next[x]];
}
nums_left -= 1;
}
//move to next element of array
x = next[x];
count++;
}
std::cout << item[last_element_index]<< " " << last_element_index<< std::endl;
}
output for
array_represent_linked_list(9,5); //item[x] =8 , next[x] = 7
JavaScript questions and answers, JavaScript questions pdf, JavaScript question bank, JavaScript questions and answers pdf, mcq on JavaScript pdf, JavaScript questions and solutions, JavaScript mcq Test , Interview JavaScript questions, JavaScript Questions for Interview, JavaScript MCQ (Multiple Choice Questions)
