Question 1 |
Consider an array of n integer with all numbers are repeated once except one number.
Example: array of size 7 as {1,5,10,5,2,1,10}, here that specific number is 2 which is not repeated.
What is the time complexity to find that number from array with constant space complexity?
Example: array of size 7 as {1,5,10,5,2,1,10}, here that specific number is 2 which is not repeated.
What is the time complexity to find that number from array with constant space complexity?
O(n) | |
O(1) | |
O(n^2)
| |
O(\log n) |
Question 1 Explanation:
We know the property of XOR that XOR of two same numbers is equal to 0 (A XOR A = 0). If we calculate the XOR of all the numbers from 1 to n (this includes the unknown missing number) and then with that result, XOR all the given numbers, the common numbers get canceled out(since A XOR A=0) and in the end we get the missing number.
Example for array of size 7
Click to Join Our Telegram Group for Latest Update of MOCK TEST 
Click Here to Practice ALL Previous MOCK TEST FREE
Example for array of size 7
int main()
{
int num=0,i,a[7]={1,5,10,5,2,1,10};
for(i=0;i<7;i++)
{
num=num^a[i];
}
printf("%d",num);
return 0;
}
Click Here to Practice ALL Previous MOCK TEST FREE
Question 2 |
Consider an array of size (n-1) with distinct integer in range from 1 to n stored randomly. In this array, one number is missing in the range of 1 to n. Time complexity to find that missing number from array with constant space complexity is
O(n) | |
O(1) | |
O(n^2)
| |
O(\log n) |
Question 2 Explanation:
You can do this in O(n).
Iterate through the array and compute the sum of all numbers. Now, sum of natural numbers from 1 to n, can be expressed as \frac{n \times (n+1)}{2}.
Subtract the sum of the array from \frac{n \times (n+1)}{2}.
Answer of substraction is the missing number.
Alternative Solution:
We can use the property of XOR to get solution for this problem without worrying about the problem of bit overflow. And also XOR is both safer and faster than summation. We know the property of XOR that XOR of two same numbers is equal to 0(A XOR A = 0). If we calculate the XOR of all the numbers from 1 to N(this includes the unknown missing number) and then with that result, XOR all the given numbers, the common numbers get canceled out(since A XOR A=0) and in the end we get the missing number. If we don't have bit overflow problem, we can use both summation and XOR based algorithms to get the solution. But, the algorithm which uses XOR is both safer and faster than the algorithm which uses summation, subtraction and multiplication. And we can avoid the additional worries caused by summation, subtraction and multiplication.
we can use XOR instead of addition and subtraction.
Lets assume, XOR(1...n) = XOR of all numbers from 1 to n
Implementation 1 => Missing Number = XOR(1...n) XOR (A[0] XOR A[1] XOR...XOR A[n-1])
Implementation 2 => Missing Number = XOR(1...N) XOR A[0] XOR A[1] XOR...XOR A[n-1]
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Iterate through the array and compute the sum of all numbers. Now, sum of natural numbers from 1 to n, can be expressed as \frac{n \times (n+1)}{2}.
Subtract the sum of the array from \frac{n \times (n+1)}{2}.
Answer of substraction is the missing number.
Alternative Solution:
We can use the property of XOR to get solution for this problem without worrying about the problem of bit overflow. And also XOR is both safer and faster than summation. We know the property of XOR that XOR of two same numbers is equal to 0(A XOR A = 0). If we calculate the XOR of all the numbers from 1 to N(this includes the unknown missing number) and then with that result, XOR all the given numbers, the common numbers get canceled out(since A XOR A=0) and in the end we get the missing number. If we don't have bit overflow problem, we can use both summation and XOR based algorithms to get the solution. But, the algorithm which uses XOR is both safer and faster than the algorithm which uses summation, subtraction and multiplication. And we can avoid the additional worries caused by summation, subtraction and multiplication.
we can use XOR instead of addition and subtraction.
Lets assume, XOR(1...n) = XOR of all numbers from 1 to n
Implementation 1 => Missing Number = XOR(1...n) XOR (A[0] XOR A[1] XOR...XOR A[n-1])
Implementation 2 => Missing Number = XOR(1...N) XOR A[0] XOR A[1] XOR...XOR A[n-1]
Click to Join Our Telegram Group for Latest Update of MOCK TEST Click Here to Practice ALL Previous MOCK TEST FREE
Question 3 |
Consider an array of size (n-2) with distinct integer in range from 1 to n stored randomly. In this array, two numbers are missing in range 1 to n. Time complexity to find that missing numbers from array with constant space complexity is
O(n) | |
O(1) | |
O(n^2)
| |
O(\log n) |
Question 3 Explanation:
Assume array to be [1,4,2,3,7] . Missing numbers are 5,6
Step 1: Add all the numbers in the array. 17. We know the sum of 1..7 ( n*(n+1)/2) = 28.
Thus x+y+17=28 => x+y=11
Step 2: Multiply all the numbers in the array. 168. We know the product of 1..7 = 5040.
Thus x*y*168 = 5040 => x*y=30
\begin{aligned} &(x+y)^2 = x^2 + 2xy + y^2 \\ & 121 = 60 + x^2 + y^2\\ & x^2 + y^2 = 61\\\\ &(x-y)^2 = x^2 - 2xy + y^2\\ & (x-y)^2 = 61 - 60\\ & (x-y)^2 = 1 \\ & x-y = 1 \end{aligned}
We have x+y=11 and x-y=1.
Solve for x,y.
we get x=6, y=5
This solution does not require additional memory space and is done in O(n).
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Step 1: Add all the numbers in the array. 17. We know the sum of 1..7 ( n*(n+1)/2) = 28.
Thus x+y+17=28 => x+y=11
Step 2: Multiply all the numbers in the array. 168. We know the product of 1..7 = 5040.
Thus x*y*168 = 5040 => x*y=30
\begin{aligned} &(x+y)^2 = x^2 + 2xy + y^2 \\ & 121 = 60 + x^2 + y^2\\ & x^2 + y^2 = 61\\\\ &(x-y)^2 = x^2 - 2xy + y^2\\ & (x-y)^2 = 61 - 60\\ & (x-y)^2 = 1 \\ & x-y = 1 \end{aligned}
We have x+y=11 and x-y=1.
Solve for x,y.
we get x=6, y=5
This solution does not require additional memory space and is done in O(n).
Click to Join Our Telegram Group for Latest Update of MOCK TEST Click Here to Practice ALL Previous MOCK TEST FREE
Question 4 |
Consider a sorted array of n elements. There is no specification regarding ascending or descending order given. What is the time complexity of searching an element from that array?
O(n) | |
O(1) | |
O(n^2)
| |
O(\log n) |
Question 4 Explanation:
Searching in sorted array can be efficient using binary search with O(log n). Binary search require the information regarding ascending or descending order of array. To find whether array is in ascending or descending order, we just have to compare first two number to find the information regarding ascending or descending order. This can be done in O(1) time. So total time complexity is O(log n).
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Click to Join Our Telegram Group for Latest Update of MOCK TEST Click Here to Practice ALL Previous MOCK TEST FREE
Question 5 |
What is the time complexity to delete number from index 7 from the array of size n?
O(n) | |
O(1) | |
O(n^2)
| |
O(\log n) |
Question 5 Explanation:
To delete number from index 7, we have to shift all number one position forward from index 8 to n-1.
Shifting of one number can be performed in O(1).
Total number of shift required is n-9.
Hence, Time complexity is O(n).
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Shifting of one number can be performed in O(1).
Total number of shift required is n-9.
Hence, Time complexity is O(n).
Click to Join Our Telegram Group for Latest Update of MOCK TEST Click Here to Practice ALL Previous MOCK TEST FREE
There are 5 questions to complete.