This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Power of a Number using Recursion in Logn Time”.
1. What will be the output for following code?
#include<stdio.h> int func(int x, int y) { if (y == 0) return 1; else if (y%2 == 0) return func(x, y/2)*func(x, y/2); else return x*func(x, y/2)*func(x, y/2); } int main() { int x = 2; int y = 3; printf("%d", func(x, y)); return 0; }
a) 9
b) 6
c) 8
d) 5
View Answer
Explanation: The given program calculates the value of x raised to power y. Thus 23 = 8.
2. What will be the time complexity of the following code which raises an integer x to the power y?
#include<stdio.h> int power(int x, int y) { if (y == 0) return 1; else if (y%2 == 0) return power(x, y/2)*power(x, y/2); else return x*power(x, y/2)*power(x, y/2); } int main() { int x = 2; int y = 3; printf("%d", power(x, y)); return 0; }
a) O(n)
b) O(log n)
c) O(n log n)
d) O(n2)
View Answer
Explanation: The recurrence relation for the above code is given by T(n)=2T(n/2)+c. By using master theorem we can calculate the result for this relation. It is found to be equal to O(n).
3. What is the space complexity of the given code?
#include<stdio.h> int power(int x, int y) { if (y == 0) return 1; else if (y%2 == 0) return power(x, y/2)*power(x, y/2); else return x*power(x, y/2)*power(x, y/2); } int main() { int x = 2; int y = 3; printf("%d", power(x, y)); return 0; }
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
View Answer
Explanation: The space complexity of the given code will be equal to O(1) as it uses only constant space in the memory.
4. Recursive program to raise an integer x to power y uses which of the following algorithm?
a) Dynamic programming
b) Backtracking
c) Divide and conquer
d) Greedy algorithm
View Answer
Explanation: The recursive approach uses divide and conquer algorithm as we break the problem into smaller parts and then solve the smaller parts and finally combine their results to get the overall solution.
5. What is the least time in which we can raise a number x to power y?
a) O(x)
b) O(y)
c) O(log x)
d) O(log y)
View Answer
Explanation: We can optimize the code for finding power of a number by calculating x raised to power y/2 only once and using it depending on whether y is even or odd.
6. What will be the time complexity of the following code?
#include<stdio.h> int power(int x, int y) { int temp; if( y == 0) return 1; temp = power(x, y/2); if (y%2 == 0) return temp*temp; else return x*temp*temp; } int main() { int x = 2; int y = 3; printf("%d", power(x, y)); return 0; }
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
View Answer
Explanation: The given code is the optimized version for finding the power of a number. It forms a recurrence relation given by T(n)=T(n/2)+c which can be solved using master theorem. It is calculated to be equal to O(log n).
7. What is the advantage of iterative code for finding power of number over recursive code?
a) Iterative code requires less time
b) Iterative code requires less space
c) Iterative code is more compiler friendly
d) It has no advantage
View Answer
Explanation: Both iterative and recursive approach can be implemented in log n time but the recursive code requires memory in call stack which makes it less preferable.
8. Which of the following correctly implements iterative code for finding power of a number?
a)
#include <stdio.h> int power(int x, int y) { int res = 1; while (y > 0) { if (y & 1) res = res * x; y = y >> 1; x = x * x; } return res; } int main() { int x = 3; unsigned int y = 5; printf("%d", power(x, y)); return 0; }
b)
#include <stdio.h> int power(int x, int y) { int res = 1; while (y > 0) { if (y && 1) res = res * x; y = y >> 1; x = x * x; } return res; } int main() { int x = 3; unsigned int y = 5; printf("%d", power(x, y)); return 0; }
c)
#include <stdio.h> int power(int x, int y) { int res = 1; while (y > 0) { if (y && 1) res = x * x; y = y >> 1; x = x * y; } return res; } int main() { int x = 3; unsigned int y = 5; printf("%d", power(x, y)); return 0; }
d)
#include <stdio.h> int power(int x, int y) { int res = 1; while (y > 0) { if (y & 1) res = x * x; y = y >> 1; x = x * y; } return res; } int main() { int x = 3; unsigned int y = 5; printf("%d", power(x, y)); return 0; }
Explanation: It represents the iterative version of required code. It has a time and space complexity of O(log n) and O(1) respectively.
9. Recursive approach to find power of a number is preferred over iterative approach.
a) True
b) False
View Answer
Explanation: The recursive code requires memory in call stack which makes it less preferable as compared to iterative approach.
10. What will be the output for following code?
float power(float x, int y) { float temp; if( y==0) return 1; temp = power(x, y/2); if (y%2 == 0) return temp*temp; else { if(y > 0) return x*temp*temp; else return (temp*temp)/x; } } int main() { float x = 2; int y = -3; printf("%f", power(x, y)); return 0; }
a) Error
b) 1/4
c) 4
d) 0.25
View Answer
Explanation: The given code is capable of handling negative powers too. Thus, the output will be 2-2 = 0.25.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Practice Computer Science MCQs
- Practice Programming MCQs
- Check Programming Books
- Practice Data Structure MCQ
- Apply for Computer Science Internship
