How would i do first and second parts?-CodePudding

Consider we have to choose a Leader from n people. For this purpose, we create an array of size n. We assign every candidate a number (1, 2, 3, 4, 5,….,n) and store it in array in ascending order. We apply dancing chair (People struggle to get the chair!!! After stopping the music, in each iteration one chair and one man is eliminated. The Final remaining one is the winner) method. Suppose we start from index 0 then we have to skip 3 indexes and we will reach at index 3. Set its value to zero and start again from index 4 and skip 3 indexes and we will reach at index 7. Repeat the same step and so on.

(1) When we reach at last index we will proceed to index 0 again (for example the last index is 19, we start the count from index 18 and skip 3 indexes then we will reach at 1 and set it to zero).

(2) If the reached element value is already 0 than set the next element to zero. Do the same process till only one element remaining?

We implement it by using array and function. Write a function SelectLeader () which takes array as input and return the Leader.

#include <stdio.h>

int SelectLeader() {
    int n, i;
    int leader = 0;
    printf("Enter total number of people to choose a Leader from: ");
    scanf("%d", &n);
    int array[n];

    for (i = 0; i < n; i  ) {
        array[i] = i   1;
    }
    for (i = 0; i <= n; i = (i   3) % n) {
        if (array[i] == 0) {
            array[(i   1) % n] = 0;
        } else
            array[i] = 0;
    }
    for (i = 0; i < n; i  ) {
        if (array[i] != 0) {
            leader = i;
        }
    }
    return leader;
}

int main() {
    int L;
    L = SelectLeader();
    printf("Leader is the candidate with the index number %d\n", L);
}

CodePudding user response：

You can use the following pesudo code

Suppose n= 10 , for easy understanding I am creating a boolean flag array to check whether number is selected or not.

jump = 3
i = 0
for (int cnt=0;cnt<10;) {

  if(flag[i] === false) {
      flag[i]=true;
      cnt =1;
      i =jump;
  }

  else {
     i =1;
  }

}

The index element remaining with flag false is ans.

However this approach is both space and time expensive.