Implement the following problem using the template listed below Magic index in a
ID: 3603042 • Letter: I
Question
Implement the following problem using the template listed below
Magic index in an array a[1..n] is defined to be an index such that a[ i ] = i. Given an array of integers, write a recursive method to find the first magic index from left to right, if one exists, in the given array or otherwise return -1.
Here are some test cases. The first number is the size of the array.
Input1
6
-2 -2 -2 -2 -2 -1
Output1
-1
-------------------------------------------
Input2
5
-1 1 2 3 4
Output2
1
import java.util.*;
class DriverMain{
public static void main(String args[]){
Scanner input = new Scanner(System.in);
int size = input.nextInt();
int a[] = new int[size];
for(int i = 0 ; i < size; i++){
a[i] = input.nextInt();
}
System.out.print(Quiz2.findMagicIndex(a));
}
class Quiz2{
public static int findMagicIndex(int[] a){
}
}
}
Explanation / Answer
import java.util.*;
class DriverMain{
public static void main(String args[]){
Scanner input = new Scanner(System.in);
int size = input.nextInt();
int a[] = new int[size];
for(int i = 0 ; i < size; i++){
a[i] = input.nextInt();
}
System.out.print(Quiz2.findMagicIndex(a));
}
static class Quiz2{
public static int findMagicIndex(int[] a){
boolean flag=false;
reverseArray(a,0,a.length-1);
for(int i=0;i<a.length;i++){
if(a[i]==1) {
flag=true;
break;
}
}
if(flag==true) return 1;
return -1;
}
static void reverseArray(int[] a, int start, int end)
{
int temp=0;
if (start >= end)
return;
temp = a[start];
a[start] = a[end];
a[end] = temp;
reverseArray(a, start+1, end-1);
}
}
}
/*case1:
6
2 3 4 5 -1 2
-1
case 2:
4
2 1 3 4
1
*/