# 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[7]={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[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

 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

 Question 6
What is the time complexity to delete number from index (n-7) from the array of size n?
 A $O(n)$ B $O(1)$ C $O(n^2)$ D $O(\log n)$
Data Structure
Question 6 Explanation:
To insert number from index n-7, we have to shift all number one position forward from index n-6 to n-1.
Shifting of one number can be performed in O(1).
Total number of shift required is 6.
Hence, Time complexity is O(1).

Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 7
What is the time complexity to insert number from index 7 from the array of size n?
NOTE: Assume array has space for that number for insert.
 A $O(n)$ B $O(1)$ C $O(n^2)$ D $O(\log n)$
Data Structure
Question 7 Explanation:
To insert number from index 7, we have to shift all number one position backward from index 7 to n-1.
Shifting of one number can be performed in O(1).
Total number of shift required is n-8.
Hence, Time complexity is O(n).

Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 8
What is the time complexity to insert number from index (n-7) from the array of size n?
NOTE: Assume array has space for that number for insert.
 A $O(n)$ B $O(1)$ C $O(n^2)$ D $O(\log n)$
Data Structure
Question 8 Explanation:
To insert number from index n-7, we have to shift all number one position backward from index n-7 to n-1.
Shifting of one number can be performed in O(1).
Total number of shift required is 7.
Hence, Time complexity is O(1).

Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 9
Consider the following declaration of a multi-dimensional array in C :

int a[4][16][4][8]

Assuming that the main memory is byte-addressable and that array is stored starting form memory address 1000 in row-major order, the address of a[2][8][2][4] is

NOTE: size of int datatype is 4 Byte.
 A 1024 B 6200 C 2048 D 5200
Data Structure
Question 9 Explanation:
For n-dimensional array declared as $int \;\; a[n_1][n_2]...[n_n]$, general formula to calculate address of any element $int \;\; a[i_1][i_2]...[i_n]$ is $=\text{Base Address of array}+ \left \{ (i_1 \times n_2 \times n_3 \times ... n_n )+ (i_2\times n_3\times n_4 \times ...n_n )+...+(i_{n-2}\times n_n ) + i_n\right \}\times sizeof({int})$
Address of a[2][8][2][4] is 1000+{(2*16*4*8)+(8*4*8)+(2*8)+4}*4 =6200

Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 10
Consider the following declaration of a multi-dimensional array in C :

int a[4][16][4][8]

Assuming that the main memory is byte-addressable and that array is stored starting form memory address 1000 in column-major order, the address of a[2][8][2][4] is
 A 2048 B 1024 C 4744 D 5744
Data Structure
Question 10 Explanation:
For n-dimensional array declared as $int \;\; a[n_1][n_2]...[n_n]$, general formula to calculate address of any element $int \;\; a[i_1][i_2]...[i_n]$ is $=\text{Base Address of array}+ \left \{ (i_n \times n_ {n-1}\times n_{n-2} \times ... n_1 )+ (i_{n-1}\times n_{n-2}\times n_{n-3} \times ...n_1 )+...+(i_2\times n_1 ) + i_1 \right \}\times sizeof({int})$
Address of a[2][8][2][4] is 1000+{(4*4*16*4)+(2*16*4)+(8*4)+2}*4 =5744

Click to Join Our Telegram Group for Latest Update of MOCK TEST