Data Structure Questions and Answers – Number of Jumps to Reach End-array Operation

«
»

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Number of Jumps to Reach End-array Operation”.

1. What will be the minimum number of jumps required to reach the end of the array arr[] = {1,3,6,3,6,8,5}?
a) 1
b) 2
c) 3
d) not possible to reach the end
View Answer

Answer: c
Explanation: Each element of the array represents the maximum number of steps that can be taken forward from that element. If the first element is 0 then it is not possible to reach the end.
advertisement

2. What will be the minimum number of jumps required to reach the end of the array arr[] ={0,1,3,6,3,6,8,5}?
a) 1
b) 2
c) 3
d) not possible to reach the end
View Answer

Answer: d
Explanation: Each element of the array represents the maximum number of steps that can be taken forward from that element. So as the first element here is 0 so we cannot move any further from the first element. Thus, it is not possible to reach the end of the array.

3. What will be the output of the following code?

advertisement
advertisement
#include <bits/stdc++.h> 
using namespace std; 
 
int func(int arr[], int s, int e) 
{
   if (s == e) 
	return 0; 
   if (arr[s] == 0) 
	return INT_MAX; 
 
int min = INT_MAX; 
for (int i = s + 1; i <= e && i <= s + arr[s]; i++) 
{ 
	int jumps = func(arr, i, e); 
	if(jumps != INT_MAX && jumps + 1 < min) 
		min = jumps + 1; 
} 
return min; 
}
 
int main() 
{ 
	int arr[] = {1, 3, 6, 3, 8, 5}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	cout << func(arr, 0, n-1); 
	return 0; 
}

a) 1
b) 2
c) 3
d) error
View Answer

Answer: c
Explanation: The given code finds the minimum number of steps required to reach the end of the array by using recursion. So the output will be 3.
advertisement

4. What will be the output of the following code?

#include <bits/stdc++.h> 
using namespace std; 
 
int min(int x, int y) 
{ return (x < y)? x: y; } 
 
int func(int arr[], int n) 
{ 
 
	int *jump = new int[n]; 
	int i, j; 
 
	if (n == 0 || arr[0] == 0) 
		return INT_MAX; 
 
	jump[0] = 0; 
 
	for (i = 1; i < n; i++) 
	{ 
		jump[i] = INT_MAX; 
		for (j = 0; j < i; j++) 
		{ 
			if (i <= j + arr[j] && jumps[j] != INT_MAX) 
			{ 
				jump[i] = min(jump[i], jump[j] + 1); 
				break; 
			} 
		} 
	} 
	return jump[n-1]; 
} 
 
int main() 
{ 
	int arr[] = {1, 3, 6, 1, 9,7}; 
	int size = sizeof(arr)/sizeof(int); 
	cout<< func(arr,size); 
	return 0; 
}

a) 1
b) 2
c) 3
d) error
View Answer

Answer: c
Explanation: The given code finds the minimum number of steps required to reach the end of the array by using dynamic programming. So the output will be 3.
advertisement

5. What will be the time complexity of the following code?

advertisement
#include <bits/stdc++.h> 
using namespace std; 
 
int min(int x, int y) 
{ return (x < y)? x: y; } 
 
int func(int arr[], int n) 
{ 
 
	int *jump = new int[n]; 
	int i, j; 
 
	if (n == 0 || arr[0] == 0) 
		return INT_MAX; 
 
	jump[0] = 0; 
 
	for (i = 1; i < n; i++) 
	{ 
		jump[i] = INT_MAX; 
		for (j = 0; j < i; j++) 
		{ 
			if (i <= j + arr[j] && jumps[j] != INT_MAX) 
			{ 
				jump[i] = min(jump[i], jump[j] + 1); 
				break; 
			} 
		} 
	} 
	return jump[n-1]; 
} 
 
int main() 
{ 
	int arr[] = {1, 3, 6, 1, 9,7}; 
	int size = sizeof(arr)/sizeof(int); 
	cout<< func(arr,size); 
	return 0; 
}

a) O(n log n)
b) O(n)
c) O(n1/2)
d) O(n2)
View Answer

Answer: d
Explanation: The given code finds the minimum number of steps required to reach the end of an array by using dynamic programming. As there is a nested loop in the code so the time complexity will be O(n2).

6. What will be the minimum number of jumps required to reach the end of the array arr[] = {1,2,0,0,3,6,8,5}?
a) 1
b) 2
c) 3
d) not possible to reach the end
View Answer

Answer: d
Explanation: Each element of the array represents the maximum number of steps that can be taken forward from that element. So we cannot move any further after reaching the second element hence it is impossible to reach the end of the array.

7. It is not possible to find the minimum number of steps to reach the end of an array in linear time.
a) true
b) false
View Answer

Answer: b
Explanation: It is possible to find the minimum number of steps to reach the end of an array in O(n) time complexity. So it is the fastest possible method of finding the minimum number of steps to reach the end of an array.

8. In how many different ways we can reach the end of the array arr[]={1,3,5,8,9}?
a) 1
b) 2
c) 3
d) 4
View Answer

Answer: d
Explanation: There are 4 possible ways in which we can reach the end of the array. The possible paths are – 1->3->5->8->9, 1->3->5->9, 1->3->8->9, 1->3->9.

9. What will be the output of the following code?

#include <bits/stdc++.h> 
using namespace std; 
 
void func(int arr[], int n) 
{  
	int count[n]; 
	memset(count, 0, sizeof(count)); 
 
	for (int i=n-2; i>=0; i--) 
	{ 
		if (arr[i] >= n - i - 1) 
			count[i]++; 
 
		for (int j=i+1; j < n-1 && j <= arr[i] + i; j++) 
 
			if (count[j] != -1) 
				count[i] += count[j]; 
 
		if (count[i] == 0) 
			count[i] = -1; 
	} 
 
	for (int i=0; i<n; i++) 
		cout << count[i] << " "; 
} 
 
int main() 
{ 
	int arr[] = {1, 3, 5, 8, 9}; 
	int n = sizeof(arr) / sizeof(arr[0]); 
	func(arr, n); 
	return 0; 
}

a) 3
b) 4
c) 4 4 2 1 0
d) 4 2 2 0 1
View Answer

Answer: c
Explanation: The given code finds the number of possible ways to reach the end of an array from each element. So the output will be 4 4 2 1 0.

10. What will be the worst case time complexity of the following code?

#include <bits/stdc++.h> 
using namespace std; 
 
void func(int arr[], int n) 
{  	
	int count[n]; 
	memset(count, 0, sizeof(count)); 
 
	for (int i=n-2; i>=0; i--) 
	{ 
		if (arr[i] >= n - i - 1) 
			count[i]++; 
 
		for (int j=i+1; j < n-1 && j <= arr[i] + i; j++) 
 
			if (count[j] != -1) 
				count[i] += count[j]; 
 
		if (count[i] == 0) 
			count[i] = -1; 
	} 
 
	for (int i=0; i<n; i++) 
		cout << count[i] << " "; 
} 
 
 
int main() 
{ 
	int arr[] = {1, 3, 5, 8, 9}; 
	int n = sizeof(arr) / sizeof(arr[0]); 
	func(arr, n); 
	return 0; 
}

a) O(n1/2)
b) O(n)
c) O(n3/2)
d) O(n2)
View Answer

Answer: d
Explanation: The given code finds the number of possible ways to reach the end of an array from each element. By observing the nested loop in the code we can say that the worst case time complexity will be O(n2).

11. : It is not possible to reach the end of an array if starting element of the array is 0.
a) true
b) false
View Answer

Answer: a
Explanation: If the first element of an array is 0 then it is not possible to reach the end. However, if 0 is present at other positions then we may/may not be able to reach the end.

12. What is the minimum possible time complexity to find the number of steps to reach the end of an array?
a) O(n)
b) O(n2)
c) O(n3/2)
d) O(1)
View Answer

Answer: a
Explanation: The minimum possible time complexity to reach the end of an array is O(n). So a linear time complexity is possible.

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter