# Co-ordinate Compression Multiple choice Questions and Answers (MCQs)

## Click on any option to know the CORRECT ANSWERS

 Question 1
What is co-ordinate compression?
 A process of reassigning co-ordinates to remove gaps B inserting gaps in a co-ordinate system C removing redundant co-ordinates D adding extra gaps

Question 1 Explanation:
Co-ordinate compression is the process of reassigning co-ordinates in order to remove gaps. This helps in improving efficiency of a solution.

 Question 2
What is the need for co-ordinate compression?
 A for improving time complexity B for improving space complexity C for improving both time and space complexity D for making code simpler

Question 2 Explanation:
Co-ordinate compression is the process of reassigning co-ordinates in order to remove gaps. This helps in improving both time and space complexity of a solution.

 Question 3
What is the output for the following code?

#include <bits/stdc++.h>  using namespace std; void convert(int a[],  int n) { 	 	vector <pair<int,  int> > vec;	 	for (int i = 0; i < n; i++) 		vec.push....back(make....pair(a[i],  i)); 	sort(vec.begin(),  vec.end()); 	 	for (int i=0; i<n; i++) 		a[vec[i].second] = i; } void printArr(int a[],  int n) { 	for (int i=0; i<n; i++) 		cout << a[i] << " "; } int main() { 	int arr[] = {10, 8, 2, 5, 7}; 	int n = sizeof(arr)/sizeof(arr); 	convert(arr ,  n); 	printArr(arr,  n); 	return 0; }
 A 4 3 0 1 2 B 1 2 3 4 5 C 5 4 1 2 3 D 0 1 2 3 4

Question 3 Explanation:
The given code converts the elements of the input array. They are replaced with their respective position number in the sorted array.

 Question 4
What will be the time complexity of given code?

#include <bits/stdc++.h>  using namespace std; void convert(int a[],  int n) { 	 	vector <pair<int,  int> > vec; 	 	for (int i = 0; i < n; i++) 		vec.push....back(make....pair(a[i],  i)); 	 	sort(vec.begin(),  vec.end()); 	 	for (int i=0; i<n; i++) 		a[vec[i].second] = i; } void printArr(int a[],  int n) { 	for (int i=0; i<n; i++) 		cout << a[i] << " "; } int main() { 	int arr[] = {10, 8, 2, 5, 7}; 	int n = sizeof(arr)/sizeof(arr); 	 	convert(arr ,  n); 	printArr(arr,  n); 	return 0; }
 A O(n) B O(n log n) C O(n2) D O(log n)

Question 4 Explanation:
The time complexity of the given code will be governed by the time complexity of the sorting algorithm used. As this code uses in built sorting of C++ so it will take O(n log n) time.

 Question 5
What is the auxiliary space complexity of the given code?

#include <bits/stdc++.h>  using namespace std; void convert(int a[],  int n) { 	 	vector <pair<int,  int> > vec; 	 	for (int i = 0; i < n; i++) 		vec.push....back(make....pair(a[i],  i)); 	 	sort(vec.begin(),  vec.end()); 	for (int i=0; i<n; i++) 		a[vec[i].second] = i; } void printArr(int a[],  int n) { 	for (int i=0; i<n; i++) 		cout << a[i] << " "; } int main() { 	int arr[] = {10, 8, 2, 5, 7}; 	int n = sizeof(arr)/sizeof(arr); 	convert(arr ,  n); 	printArr(arr,  n); 	return 0; }
 A O(1) B O(n) C O(log n) D O(n log n)