Problem 1 There are n items, numbered from 1 to n in a given array and given a p
ID: 671480 • Letter: P
Question
Problem 1 There are n items, numbered from 1 to n in a given array and given a positive integer number k (k < n). We start from item number 1 and delete from the array the item number k and so on until one item remains. The task is to output the initial position of this remaining item. For example, if we have an array = [1, 2, 3, 4, 5, 6, 7], n = 7 and k = 3, then the numbers 3, 6, 2, 7, 5, 1 are deleted in order, and the number 4 survives.
(a) Implement a recursive function in Java int lastsurvivor(int arr[], int n, int k) that simulates this process and returns the location of the last survivor in a given array.
(b) What is the running time complexity of your function? Justify
Explanation / Answer
(a) Java Code:
public class LastSurviver {
public static int lastsurvivor(int arr[], int n, int k) {
if (n == 1) {
return arr[0]; // return the last surviving value
} else {
//reursively call method lastsurvivor()
return (lastsurvivor(arr, n - 1, k) + k - 1) % n + 1;
}
}
// utility method for the position
public static int pos(int arr[], int n, int k) {
return lastsurvivor(arr, n, k) - 1;
}
// tests the lastSurvivor function
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
int k = 3;
int lastSurvivorPosition=pos(arr, arr.length, k);
System.out.println("Last Survivor's Position is "+lastSurvivorPosition+" i.e Number "+arr[lastSurvivorPosition]);
}
}
(b) Complexity:
return (lastsurvivor(arr, n - 1, k) + k - 1) % n + 1;
Recursive function will get called n times and when n==1 i.e last survivor it wil stop and return.
Therefore time complexity will be O(n)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.