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

Uncategorized

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 time complexity 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) O(n log n)
B) O(n)
C) O(n1/2)
D) O(n2)

Explanation: Using dynamic programming, the given code determines the smallest number of steps needed to reach the end of an array. Since the code contains a nested loop, the time complexity will be O. (n2).

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

Explanation: The maximum number of steps that can be taken forward from each element of the array is represented by each element of the array. As a result, after reaching the second portion, we are unable to progress any further, making reaching the end of the array impossible.

3. 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

Explanation: In O(n) time complexity, the smallest number of steps to reach the end of an array can be found. As a result, it is the quickest method for determining the smallest number of steps required to reach the end of an array.

4. 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

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.

5. 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

Explanation: The provided code calculates the number of possible paths from each element to the end of an array. As a result, the final result will be 4 4 2 1 0.

6. 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)

Explanation: The provided code calculates the number of possible paths from each element to the end of an array. We can deduce from the code’s nested loop that the worst-case time complexity is O. (n2).

7. It is not possible to reach the end of an array if starting element of the array is 0.
A) true
B) false

Explanation: It is impossible to reach the end of an array if the first element is 0. If 0, on the other hand, is present in other places, we may or may not be able to hit the end.

8. 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)

Explanation: To reach the end of an array, the smallest possible time complexity is O. (n). As a result, a linear time complexity can be achieved.

9. 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

Explanation: The maximum number of steps that can be taken forward from each element of the array is represented by each element of the array. It is impossible to reach the end if the first factor is 0.

10. 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

Explanation: The maximum number of steps that can be taken forward from each element of the array is represented by each element of the array. We can’t go any further from the first factor because it’s 0 in this case. As a result, getting to the end of the array is impossible.

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

#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

Explanation: Using recursion, the given code determines the smallest number of steps needed to reach the end of the array. As a result, the result will3.advertisementhttps://a7d65673dba734a83f62e0bb059cc899.safeframe.googlesyndication.com/safeframe/1-0-38/html/container.html

12. 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

Explanation: Using dynamic programming, the given code determines the smallest number of steps needed to reach the end of the array. As a result, the production will be 3.

The end() function transfers the internal pointer to the last element in the array and outputs it. Methods that are similar: current() returns the value of the current array element. next() – transfers the internal pointer to the next element in the array and outputs it. There is no end marker in C arrays. As the programmer, it is your duty to keep track of the array’s allocated size and ensure that no elements are accessed outside of that size. If you try to access an element outside of its allocated size, you’ll get unexpected results.

Leave a Reply

Your email address will not be published. Required fields are marked *