Problem #2. There are n items, numbered from 1 to n in a given array and given a

Question

Problem #2.
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.
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.

Explanation / Answer

import java.util.*;
public class HelloWorld {
public static int lastSurvivor(int array[], int n, int k) {
if (n == 1) {
return array[0];
} else {
return ((lastSurvivor(array, n-1, k) + k-1 ) % n)+1;
}
}
public static int lastSurvivorPosition(int array[], int n, int k)
{
return (lastSurvivor(array, n, k));
}
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
int array[] =new int[100];
int n1=s.nextInt();
int k1=s.nextInt();
int j=0;
for(int i=1;i<=n1;i++)
{
array[j]=i;
j++;
}
System.out.println("Answer: " + lastSurvivorPosition(array, n1, k1));
}
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.