** Contains only technical mcq and programming **
Technical Mcq :
1. b
2. b
3. c
4. b
5. a
6. b
7. b
8. b
9. a
10. c
***********************************************************
Programming :
1.
Problem Statement
Given an array of N integers, and an integer K, find the number of pairs of elements in the array whose
sum is equal to K.
Input Format
First line of input contains two space separate integers 'n' and 'k'.
Next line of input contains n integers - the elements of the array.
Constraints
1 <= N <= 105 1 <= K <= 108 1 <= Arri <= 106
Output Format
Print the number of pairs that have sum K.
C++ :
#include <bits/stdc++.h>
using namespace std;
int pairs_count(int arr[], int n, int sum)
{
int ans = 0;
sort(arr, arr + n);
int i = 0, j = n - 1;
while (i < j) {
if (arr[i] + arr[j] < sum)
i++;
else if (arr[i] + arr[j] > sum)
j--;
else {
int x = arr[i], xx = i;
while (i < j and arr[i] == x)
i++;
int y = arr[j], yy = j;
while (j >= i and arr[j] == y)
j--;
if (x == y) {
int temp = i - xx + yy - j - 1;
ans += (temp * (temp + 1)) / 2;
}
else
ans += (i - xx) * (yy - j);
}
}
return ans;
}
int main()
{int n,k;cin>>n>>k;int arr[n];
for(int i=0;i<n;i++)
{ cin>>arr[i];
}
cout << pairs_count(arr, n, k);
return 0;
}
******************************************************
2.
Problem Statement
Given an array of items, the i'th index element denotes the item id’s and given a number m, the task
is to remove m elements such that there should be minimum distinct id’s left. Print the number of
distinct id’s.
Input Format
First line of input contains 'n' the size of array. Next line contains n integers which are the elements
of the array. Next line contains an integer 'm'
Constraints
1<=n<=10000 -10000<=elements of array<=100000 1<=m<=1000
Output Format
Print the number of distinct id’s left
C++ CODE:
#include <bits/stdc++.h>
using namespace std;
int distinctNumbers(int arr[], int m,
int n)
{
unordered_map<int, int> count;
for (int i = 0; i < n; i++)
count[arr[i]]++;
vector<int> fre_arr(n + 1, 0);
for (auto it : count) {
fre_arr[it.second]++;
}
int ans = count.size();
for (int i = 1; i <= n; i++) {
int temp = fre_arr[i];
if (temp == 0)
continue;
int t = min(temp, m / i);
ans -= t;
m -= i * t;
}
return ans;
}
int main()
{int n,m;cin>>n;
int arr[n];
for(int i=0;i<n;i++)
{cin>>arr[i];
}
cin>>m;
cout << distinctNumbers(arr, m, n);
return 0;
}
*******************************************************
3.
A peak element in an array is the one that is not smaller than its neighbours. Given an array of size
N, find the index of first peak element encountered in the array.
For corner elements, we need to consider only one neighbor.
Input Format
First line contains 'n' - the size of the array. Next line contains n integers- the n elements of array.
Constraints
2<=n<=10000 1<=elements of array<=10000
Output Format
Print index of the first peak element encountered in the array
C++ CODE:
#include <bits/stdc++.h>
using namespace std;
int findPeak(int arr[], int n)
{
if (n == 1)
return 0;
if (arr[0] >= arr[1])
return 0;
if (arr[n - 1] >= arr[n - 2])
return n - 1;
for (int i = 1; i < n - 1; i++) {
if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1])
return i;
}
}
int main()
{int n;cin>>n;int arr[n];
for(int i=0;i<n;i++)cin>>arr[i];
cout << findPeak(arr, n);
return 0;
}
*****************************************************
Post a Comment