# Array Data Structure Mock Test -1

 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?
 A $O(n)$ B $O(1)$ C $O(n^2)$ D $O(\log n)$
Data Structure
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
int main()
{
int num=0,i,a={1,5,10,5,2,1,10};
for(i=0;i<7;i++)
{
num=num^a[i];
}
printf("%d",num);

return 0;
}

For array of size (n-1), Time comlexity is O(n). Click to Join Our Telegram Group for Latest Update of MOCK TEST 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
 A $O(n)$ B $O(1)$ C $O(n^2)$ D $O(\log n)$
Data Structure
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.
Lets assume, XOR(1...n) = XOR of all numbers from 1 to n
Implementation 1 => Missing Number = XOR(1...n) XOR (A XOR A XOR...XOR A[n-1])
Implementation 2 => Missing Number = XOR(1...N) XOR A XOR A XOR...XOR A[n-1] Click to Join Our Telegram Group for Latest Update of MOCK TEST 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
 A $O(n)$ B $O(1)$ C $O(n^2)$ D $O(\log n)$
Data Structure
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 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?
 A $O(n)$ B $O(1)$ C $O(n^2)$ D $O(\log n)$
Data Structure
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 Question 5
What is the time complexity to delete number from index 7 from the array of size n?
 A $O(n)$ B $O(1)$ C $O(n^2)$ D $O(\log n)$
Data Structure
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 