![[Solved] Searching Algorithms Problem](https://realcoder.techss24.com/wp-content/uploads/2022/06/Solved-Searching-Algorithms-Problem.png "[Solved] Searching Algorithms Problem")
Searching Algorithms: Linear Search, Binary Search, and Ternary Search.
1. Search an Element in an array
Given an integer array and another integer element. The task is to find if the given element is present in array or not.
Example 1:
Input:
n = 4
arr[] = {1,2,3,4}
x = 3
Output: 2
Explanation: There is one test case
with array as {1, 2, 3 4} and element
to be searched as 3. Since 3 is
present at index 2, output is 2.Example 2:
Input:
n = 5
arr[] = {1,2,3,4,5}
x = 5
Output: 4
Explanation: For array elements
{1,2,3,4,5} element to be searched
is 5 and it is at index 4. So, the
output is 4.
Your Task:
The task is to complete the function search() which takes the array arr[], its size N and the element X as inputs and returns the index of first occurrence of X in the given array. If the element X does not exist in the array, the function should return -1.
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1).
Constraints:
1 <= n <= 106
0 <= arr[i] <= 106
0 <= x <= 105
Solution
// { Driver Code Starts
//Initial Template for C
#include<stdio.h>
// } Driver Code Ends
//User function Template for C
int search(int arr[], int N, int X)
{
// Your code here
for(int i=0;i<N;i++){
if(arr[i]==X)
return i;
}
return -1;
}
// { Driver Code Starts.
int main()
{
int testcases;
scanf("%d", &testcases);
while(testcases--)
{
int sizeOfArray;
scanf("%d", &sizeOfArray);
int arr[sizeOfArray];
int x;
for(int i=0;i<sizeOfArray;i++)
{
scanf("%d", &arr[i]);
}
scanf("%d", &x);
printf("%d\n", search(arr,sizeOfArray,x)); //Linear search
}
return 0;
}
// } Driver Code Ends2. Searching an element in a sorted array
Given an array arr[] sorted in ascending order of size N and an integer K. Check if K is present in the array or not.
Example 1:
Input:
N = 5, K = 6
arr[] = {1,2,3,4,6}
Output: 1
Exlpanation: Since, 6 is present in
the array at index 4 (0-based indexing),
output is 1.Example 2:
Input:
N = 5, K = 2
arr[] = {1,3,4,5,6}
Output: -1
Exlpanation: Since, 2 is not present
in the array, output is -1.
Your Task:
You don’t need to read input or print anything. Complete the function searchInSorted() which takes the sorted array arr[], its size N and the element K as input parameters and returns 1 if K is present in the array, else it returns -1.
Expected Time Complexity: O(Log N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 106
1 <= K <= 106
1 <= arr[i] <= 106
Solution
// { Driver Code Starts
//Initial Template for C
#include <stdio.h>
// } Driver Code Ends
//User function Template for C
int searchInSorted(int arr[], int N, int K)
{
// Your code here
// Your code here
int l =0;
int h = N-1;
while(l<=h){
int mid = (l+h)/2;
if(arr[mid] == K){
return 1;
}
else if(K>arr[mid]){
l = mid+1;
}
else{
h = mid-1;
}
}
return -1;
}
// { Driver Code Starts.
int main(void)
{
int t;
scanf("%d", &t);
while(t--){
int n, k;
scanf("%d%d", &n, &k);
int arr[n];
for(int i = 0;i<n;i++){
scanf("%d", &arr[i]);
}
printf("%d\n", searchInSorted(arr, n, k));
}
return 0;
}
// } Driver Code Ends3. Count 1’s in binary array
Given a binary sorted non-increasing array of 1s and 0s. You need to print the count of 1s in the binary array.
Example 1:
Input:
N = 8
arr[] = {1,1,1,1,1,0,0,0}
Output: 5
Explanation: Number of 1's in given
binary array : 1 1 1 1 1 0 0 0 is 5.Example 2:
Input:
N = 8
arr[] = {1,1,0,0,0,0,0,0}
Output: 2
Explanation: Number of 1's in given
binary array : 1 1 0 0 0 0 0 0 is 2.
Your Task:
The task is to complete the function countOne() which takes the array arr[] and its size N as inputs and returns the count of 1s in the input array.
Expected Time Complexity: O(LogN).
Expected Auxiliary Space: O(1).
Constraint:
1 <= N <= 5*106
arr[i] = 0,1
Solution
// { Driver Code Starts
#include <bits/stdc++.h>
using namespace std;
// } Driver Code Ends
class Solution{
public :
int cnt(int arr[],int n)
{
int low =0;
int high=n-1;
int mid;
while(low<=high)
{mid=(low+high);
if(arr[mid]>1)
{
high=mid-1;
}
else if(arr[mid]<1)
{
low=mid+1;
}
else
{
if(mid==0 || arr[mid-1]!=arr[mid])
return mid;
else high=mid-1;
}
}
return -1;
}
public:
// Function to count number of Ones
// arr: input array
// N: size of input array
int countOnes(int arr[], int N)
{
// Your code here
sort(arr,arr+N);
int index=cnt(arr,N);
if(index==-1) return 0;
return N-index;
}
};
// { Driver Code Starts.
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int *arr = new int[n];
for(int i = 0; i < n; i++)
cin>>arr[i];
Solution ob;
cout <<ob.countOnes(arr, n)<<endl;
}
return 0;
} // } Driver Code Ends4. Square root of a number
Given an integer x, find the square root of x. If x is not a perfect square, then return floor(√x).
Example 1:
Input: x = 5 Output: 2 Explanation: Since, 5 is not a perfect square, floor of square_root of 5 is 2.
Example 2:
Input: x = 4 Output: 2 Explanation: Since, 4 is a perfect square, so its square root is 2.
Your Task:
You don’t need to read input or print anything. The task is to complete the function floorSqrt() which takes x as the input parameter and return its square root.
Note: Try Solving the question without using the sqrt function. The value of x>=0.
Expected Time Complexity: O(log N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ x ≤ 107
Solution
// { Driver Code Starts
#include<bits/stdc++.h>
using namespace std;
// } Driver Code Ends
// Function to find square root
// x: element to find square root
class Solution{
public:
long long int floorSqrt(long long int x)
{
// Your code goes here
}
};
// { Driver Code Starts.
int main()
{
int t;
cin>>t;
while(t--)
{
long long n;
cin>>n;
Solution obj;
cout << obj.floorSqrt(n) << endl;
}
return 0;
}
// } Driver Code Ends5. Majority Element
Given an array A of N elements. Find the majority element in the array. A majority element in an array A of size N is an element that appears more than N/2 times in the array.
Example 1:
Input:
N = 3
A[] = {1,2,3}
Output:
-1
Explanation:
Since, each element in
{1,2,3} appears only once so there
is no majority element.
Example 2:
Input:
N = 5
A[] = {3,1,3,3,2}
Output:
3
Explanation:
Since, 3 is present more
than N/2 times, so it is
the majority element.
Your Task:
The task is to complete the function majorityElement() which returns the majority element in the array. If no majority exists, return -1.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 107
0 ≤ Ai ≤ 106
Solution
// { Driver Code Starts
//Initial template for C++
#include<bits/stdc++.h>
using namespace std;
// } Driver Code Ends
//User function template for C++
class Solution{
public:
// Function to find majority element in the array
// a: input array
// size: size of input array
int majorityElement(int a[], int size)
{
// your code here
map<int,int>m;
for(int i=0;i<size;i++)
m[a[i]]++;
for(auto it:m){
if(it.second>size/2) return it.first;
}
return -1;
}
};
// { Driver Code Starts.
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int arr[n];
for(int i = 0;i<n;i++){
cin >> arr[i];
}
Solution obj;
cout << obj.majorityElement(arr, n) << endl;
}
return 0;
}
// } Driver Code Ends6. Left Index
Given a sorted array of positive integers (elements may be repeated) and a number x. The task is to find the leftmost index of x in the given array.
Example 1:
Input:
N = 10
arr[] = {1,1,2,2,3,4,5,5,6,7}
x = 1
Output: 0
Explanation: 1 is present two times
in the array and its leftmost index
is 0.Example 2:
Input:
N = 7
arr[] = {10,20,20,20,20,20,20}
x = 20
Output: 1
Explanation: 20 is present 5 time,
but its leftmost index is 1.
Your Task:
The task is to complete the function leftIndex() which takes the array arr[], its size N and an integer x as inputs and returns the index of leftmost occurrence of x in given input array. It returns -1 if element is not present in the array.
Expected Time Complexity: O(LogN).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 106
1 <= arr[i] <= 106
1 <= x <= 106
Solution
// { Driver Code Starts
#include <iostream>
using namespace std;
// } Driver Code Ends
// Function to find element in sorted array
int leftIndex(int N, int arr[], int X){
// Your code here
int low=0;
int high=N-1;
int mid;
while(low<=high)
{
mid=(low+high)/2;
if(arr[mid]>X) high=mid-1;
else if(arr[mid]<X) low=mid+1;
else
{
if(mid==0 || arr[mid-1]!=arr[mid])
return mid;
else
high=mid-1;
}
}
return -1;
}
// { Driver Code Starts.
// Driver Code
int main() {
// Testcase input
int testcases;
cin >> testcases;
// Looping through all testcases
while(testcases--){
int sizeOfArray;
cin >> sizeOfArray;
int arr[sizeOfArray];
// Array input
for(int index = 0; index < sizeOfArray; index++){
cin >> arr[index];
}
int elemntToSearch;
cin >> elemntToSearch;
cout << leftIndex(sizeOfArray, arr, elemntToSearch) << endl;
}
return 0;
} // } Driver Code Ends7. Peak element
An element is called a peak element if its value is not smaller than the value of its adjacent elements(if they exists).
Given an array arr[] of size N, Return the index of any one of its peak elements.
Note: The generated output will always be 1 if the index that you return is correct. Otherwise output will be 0.
Example 1:
Input:
N = 3
arr[] = {1,2,3}
Possible Answer: 2
Generated Output: 1
Explanation: index 2 is 3.
It is the peak element as it is
greater than its neighbour 2.
If 2 is returned then the generated output will be 1 else 0.
Example 2:
Input:
N = 2
arr[] = {3,4}
Possible Answer: 1
Output: 1
Explanation: 4 (at index 1) is the
peak element as it is greater than
its only neighbour element 3.
If 2 is returned then the generated output will be 1 else 0.
Your Task:
You don’t have to read input or print anything. Complete the function peakElement() which takes the array arr[] and its size N as input parameters and return the index of any one of its peak elements.
Can you solve the problem in expected time complexity?
Expected Time Complexity: O(log N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 105
1 ≤ A[] ≤ 106
Solution
// { Driver Code Starts
#include<bits/stdc++.h>
using namespace std;
// } Driver Code Ends
/* The function should return the index of any
peak element present in the array */
// arr: input array
// n: size of array
class Solution
{
public:
int peakElement(int arr[], int n)
{
// Your code here
for(int i=0;i<n;i++){
if((i==0 || arr[i] >= arr[i-1]) && (i==n-1 || arr[i]>=arr[i+1])){
return i;
}
}
return -1;
}
};
// { Driver Code Starts.
int main() {
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int a[n], tmp[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
tmp[i] = a[i];
}
bool f=0;
Solution ob;
int A = ob. peakElement(tmp,n);
if(A<0 and A>=n)
cout<<0<<endl;
else
{
if(n==1 and A==0)
f=1;
else if(A==0 and a[0]>=a[1])
f=1;
else if(A==n-1 and a[n-1]>=a[n-2])
f=1;
else if(a[A]>=a[A+1] and a[A]>= a[A-1])
f=1;
else
f=0;
cout<<f<<endl;
}
}
return 0;
} // } Driver Code Ends8. Floor in a Sorted Array
Given a sorted array arr[] of size N without duplicates, and given a value x. Floor of x is defined as the largest element K in arr[] such that K is smaller than or equal to x. Find the index of K(0-based indexing).
Example 1:
Input:
N = 7, x = 0
arr[] = {1,2,8,10,11,12,19}
Output: -1
Explanation: No element less
than 0 is found. So output
is "-1".Example 2:
Input:
N = 7, x = 5
arr[] = {1,2,8,10,11,12,19}
Output: 1
Explanation: Largest Number less than 5 is
2 (i.e K = 2), whose index is 1(0-based
indexing).
Your Task:
The task is to complete the function findFloor() which returns an integer denoting the index value of K or return -1 if there isn’t any such number.
Expected Time Complexity: O(log N).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 107
1 ≤ arr[i] ≤ 1018
0 ≤ X ≤ arr[n-1]
Solution
// { Driver Code Starts
#include <bits/stdc++.h>
using namespace std;
// } Driver Code Ends
class Solution{
public:
// Function to find floor of x
// n: size of vector
// x: element whose floor is to find
int findFloor(vector<long long> v, long long n, long long x){
// Your code here
int i=0;
while(v[i]<=x && i<n){
i++;
}
return i-1;
}
};
// { Driver Code Starts.
int main() {
long long t;
cin >> t;
while(t--){
long long n;
cin >> n;
long long x;
cin >> x;
vector<long long> v;
for(long long i = 0;i<n;i++){
long long temp;
cin >> temp;
v.push_back(temp);
}
Solution obj;
cout << obj.findFloor(v, n, x) << endl;
}
return 0;
} // } Driver Code Ends9. Minimum Number in a sorted rotated array
Given an array of distinct elements which was initially sorted. This array is rotated at some unknown point. The task is to find the minimum element in the given sorted and rotated array.
Example 1:
Input:
N = 10
arr[] = {2,3,4,5,6,7,8,9,10,1}
Output: 1
Explanation: The array is rotated
once anti-clockwise. So minium
element is at last index (n-1)
which is 1.Example 2:
Input:
N = 5
arr[] = {3,4,5,1,2}
Output: 1
Explanation: The array is rotated
and the minimum element present is
at index (n-2) which is 1.
Your Task:
The task is to complete the function minNumber() which takes the array arr[] and its starting and ending indices (low and high) as inputs and returns the minimum element in the given sorted and rotated array.
Expected Time Complexity: O(LogN).
Expected Auxiliary Space: O(LogN).
Constraints:
1 <= N <= 107
1 <= arr[i] <= 107
Solution
// { Driver Code Starts
//Initial Template for C
#include <stdio.h>
// } Driver Code Ends
//User function Template for C
//Function to find the minimum element in sorted and rotated array.
int minNumber(int arr[], int low, int high)
{
// Your code here
int mid;
while(low<=high)
{
mid=low+(high-low)/2;
if(arr[mid]>arr[high])
{
low=mid+1;
}
else if(arr[mid]<arr[low])
{
high=mid;
}
else
return arr[low];
}
}
// { Driver Code Starts.
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
int n;
scanf("%d", &n);
int a[n];
for(int i=0;i<n;++i)
scanf("%d", &a[i]);
printf("%d\n", minNumber(a,0,n-1) );
}
return 0;
} // } Driver Code Ends10. Two Repeated Elements
You are given an array of N+2 integer elements. All elements of the array are in range 1 to N. Also, all elements occur once except two numbers which occur twice. Find the two repeating numbers.
Example 1:
Input:
N = 4
array[] = {1,2,1,3,4,3}
Output: 1 3
Explanation: In the given array,
1 and 3 are repeated two times.Example 2:
Input:
N = 2
array[] = {1,2,2,1}
Output: 2 1
Explanation: In the given array,
1 and 2 are repeated two times
and second occurence of 2 comes
before 1. So the output is 2 1.
Your Task:
The task is to complete the function repeatedElements() which takes array arr[] and an integer N as inputs (the size of the array is N + 2 and elements are in range[1, N]) and finds the two repeated element in the array and return them in a list.
Note: Return the numbers in their order of appearing twice. So, if X and Y are the repeating numbers, and X repeats twice before Y repeating twice, then the order should be (X,Y).
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
2 ≤ N ≤ 105
1 ≤ array[i] ≤ N
Solution
// { Driver Code Starts
//Initial template for C++
#include<bits/stdc++.h>
using namespace std;
// } Driver Code Ends
//User function template for C++
class Solution {
public:
//Function to find two repeated elements.
vector<int> twoRepeated (int arr[], int N) {
// Your code here
vector<int> ans;
//this is an intra hashing way
for(int i=0; i<N+2; i++){
if(arr[abs(arr[i])] > 0){
arr[abs(arr[i])] = -1*arr[abs(arr[i])];
}
else{
ans.push_back(abs(arr[i]));
}
}
return ans;
}
};
// { Driver Code Starts.
int main()
{
int t,n;
cin>>t;
while(t--)
{
cin>>n;
int a[n+2];
for(int i=0;i<n+2;i++)
cin>>a[i];
Solution obj;
vector<int> res;
res = obj.twoRepeated(a, n);
cout<<res[0]<<" "<<res[1]<<endl;
}
return 0;
}
// } Driver Code Ends11. Roof Top
You are given heights of consecutive buildings. You can move from the roof of a building to the roof of next adjacent building. You need to find the maximum number of consecutive steps you can put forward such that you gain an increase in altitude with each step.
Example 1:
Input:
N = 5
A[] = {1,2,2,3,2}
Output: 1
Explanation: 1, 2 or 2, 3 are the only consecutive
buildings with increasing heights thus maximum number
of consecutive steps with increase in gain in altitude
would be 1 in both cases.
Example 2:
Input:
N = 4
A[] = {1,2,3,4}
Output: 3
Explanation: 1 to 2 to 3 to 4 is the jump of
length 3 to have maximum number of
buildings with increasing heights, so maximum steps
with increasing altitude becomes 3.Your Task:
The task is to complete the function maxStep() which takes an array A[] (denoting the heights of buildings) and its size N as inputs and returns the maximum number of steps to gain increase in altitude.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 106
1 <= Ai <= 105
Solution
// { Driver Code Starts
#include <bits/stdc++.h>
using namespace std;
// } Driver Code Ends
class Solution
{
public:
//Function to find maximum number of consecutive steps
//to gain an increase in altitude with each step.
int maxStep(int A[], int N)
{
//Your code here
int l=0;
int res=0;
for(int i=0;i<N-1;i++)
{
if(A[i+1]>A[i])
{
l++;
res=max(res,l);
}
else
{
l=0;
}
}
return res;
}
};
// { Driver Code Starts.
int main() {
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
Solution ob;
cout << ob.maxStep(a, n) << endl;
}
return 0;
} // } Driver Code Ends12. Maximum Water Between Two Buildings
Given an integer array representing the heights of N buildings, the task is to delete N-2 buildings such that the water that can be trapped between the remaining two building is maximum.
Note: The total water trapped between two buildings is gap between them (number of buildings removed) multiplied by height of the smaller building.
Example 1:
Input:
N = 6
height[] = {2,1,3,4,6,5}
Output: 8
Explanation: The heights are 2 1 3 4 6 5.
So we choose the following buildings
2,5 and remove others. Now gap between
two buildings is equal to 4, and the
height of smaller one is 2. So answer is
2 * gap = 2*4 = 8. There is
no answer greater than this.
Example 2:
Input:
N = 2
height[] = {2,1}
Output: 0
Explanation: The heights are 2 1.
But there is no other buildings to be
removed so total removed= 0.
Now the height of smaller one is 2.
So answer is 2 * removed buildings = 2*0
= 0.Your Task:
You need to complete the function maxWater that takes height array and size N as parameters and returns the max water that can be stored. The printing is done by the driver code.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= heighti <= 106
1 <= N <= 105
Solution
// { Driver Code Starts
//Initial Template for C++
// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// } Driver Code Ends
//User function Template for C++
class Solution
{
public:
//Function to return the maximum water that can be stored.
int maxWater(int height[], int n)
{
int low = 0, high = n - 1;
int gap, mx = 0, mn;
while(low < high){
mn = min(height[low], height[high]);
gap = mn * (high - low - 1);
mx = max(mx, gap);
if(height[low] < height[high])
low++;
else
high--;
}
return mx;
}
};
// { Driver Code Starts.
// Driver code
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int height[n];
for(int i=0;i<n;i++)
{
cin>>height[i];
}
Solution ob;
cout<<(ob.maxWater(height, n))<<endl;
}
}
// } Driver Code Ends13. Smallest Positive missing number
You are given an array arr[] of N integers including 0. The task is to find the smallest positive number missing from the array.
Example 1:
Input:
N = 5
arr[] = {1,2,3,4,5}
Output: 6
Explanation: Smallest positive missing
number is 6.
Example 2:
Input:
N = 5
arr[] = {0,-10,1,3,-20}
Output: 2
Explanation: Smallest positive missing
number is 2.Your Task:
The task is to complete the function missingNumber() which returns the smallest positive missing number in the array.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 106
-106 <= arr[i] <= 106
Solution
// { Driver Code Starts
#include<bits/stdc++.h>
using namespace std;
// } Driver Code Ends
class Solution
{
public:
//Function to find the smallest positive number missing from the array.
int missingNumber(int nums[], int n)
{
for(int i=0;i<n;i++)
{
if(nums[i]<=0)
{
nums[i]=n+1;
}
}
for(int i=0;i<n;i++)
{
if(abs(nums[i])<=n && nums[abs(nums[i])-1]>0)
{
nums[abs(nums[i])-1]*=-1;
}
}
for(int i=0;i<n;i++)
{
if(nums[i]>0)
{
return i+1;
}
}
return n+1;
}
};
// { Driver Code Starts.
int missingNumber(int arr[], int n);
int main() {
//taking testcases
int t;
cin>>t;
while(t--){
//input number n
int n;
cin>>n;
int arr[n];
//adding elements to the array
for(int i=0; i<n; i++)cin>>arr[i];
Solution ob;
//calling missingNumber()
cout<<ob.missingNumber(arr, n)<<endl;
}
return 0;
} // } Driver Code Ends14. Count only Repeated
Given an array arr[] of N positive integers, where elements are consecutive (sorted). Also, there is a single element which is repeating X (any variable) number of times. Now, the task is to find the element which is repeated and number of times it is repeated.
Note: If there’s no repeating element, Return {-1,-1}.
Example 1:
Input:
N = 5
arr[] = {1,2,3,3,4}
Output: 3 2
Explanation: In the given array, 3 is
occuring two times.
Example 2:
Input:
N = 5
arr[] = {2,3,4,5,5}
Output: 5 2
Explanation: In the given array, 5 is
occuring two times.Example 3:
Input:
N = 3
arr[] = {1,2,3}
Output: -1 -1
Explanation: In the given array, there's no
repeating element, and thus the given Output.
Your Task:
Complete findRepeating function and return pair of element which is repeated and the number of times it is repeated. The printing is done by the driver code.
Constraints:
1 <= N <= 107
1 <= arr[i] <= 1015
Expected Time Complexity: O(logN)
Expected Auxilliary Space: O(1)
Solution
// { Driver Code Starts
//Initial function template for C++
#include <bits/stdc++.h>
using namespace std;
// } Driver Code Ends
//User function template for C++
class Solution
{
public:
//Function to find repeated element and its frequency.
pair<int, int> findRepeating(int *arr, int n){
//code here
pair<int, int> p;
p.first = -1;
p.second = -1;
if(n < 2)
return p;
int count = 0;
int element=0;
unordered_set<int>u;
for(int i=0;i<n;i++){
if(u.find(arr[i])==u.end())
u.insert(arr[i]);
else{
element=arr[i];
count++;
}
}
if (count == 0)
return p;
count++;
p.first = element;
p.second = count;
return p;
}
};
// { Driver Code Starts.
int main() {
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int arr[n];
for(int i = 0;i<n;i++){
cin >> arr[i];
}
Solution obj;
pair<int, int> ans = obj.findRepeating(arr,n);
cout << ans.first << " " << ans.second << endl;
}
} // } Driver Code Ends15. Count More than n/k Occurences
Given an array arr[] of size N and an element k. The task is to find all elements in array that appear more than n/k times.
Example 1:
Input:
N = 8
arr[] = {3,1,2,2,1,2,3,3}
k = 4
Output: 2
Explanation: In the given array, 3 and
2 are the only elements that appears
more than n/k times.
Example 2:
Input:
N = 4
arr[] = {2,3,3,2}
k = 3
Output: 2
Explanation: In the given array, 3 and 2
are the only elements that appears more
than n/k times. So the count of elements
are 2.Your Task:
The task is to complete the function countOccurence() which returns count of elements with more than n/k times appearance.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 <= N <= 104
1 <= a[i] <= 106
1 <= k <= N
Solution
// { Driver Code Starts
// A C++ program to print elements with count more than n/k
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// } Driver Code Ends
class Solution
{
public:
//Function to find all elements in array that appear more than n/k times.
int countOccurence(int arr[], int n, int k) {
// Your code here
int t=n/k;
int count=0;
unordered_map<int,int>m;
for(int i=0;i<n;i++){
m[arr[i]]++;
}
for(int i=0;i<m.size();i++){
if(m[i]>t)
count++;
}
return count;
}
};
// { Driver Code Starts.
int main() {
int t, k;
cin >> t;
while (t--) {
int n, i;
cin >> n;
int arr[n];
for (i = 0; i < n; i++) cin >> arr[i];
cin >> k;
Solution obj;
cout << obj.countOccurence(arr, n, k) << endl;
}
return 0;
}
// } Driver Code Ends16. Allocate minimum number of pages
You are given N number of books. Every ith book has Ai number of pages. The books are arranged in ascending order.
You have to allocate contiguous books to M number of students. There can be many ways or permutations to do so. In each permutation, one of the M students will be allocated the maximum number of pages. Out of all these permutations, the task is to find that particular permutation in which the maximum number of pages allocated to a student is the minimum of those in all the other permutations and print this minimum value.
Each book will be allocated to exactly one student. Each student has to be allocated at least one book.
Note: Return -1 if a valid assignment is not possible, and allotment should be in contiguous order (see the explanation for better understanding).
Example 1:
Input:
N = 4
A[] = {12,34,67,90}
M = 2
Output:113
Explanation:Allocation can be done in
following ways:{12} and {34, 67, 90}
Maximum Pages = 191{12, 34} and {67, 90}
Maximum Pages = 157{12, 34, 67} and {90}
Maximum Pages =113. Therefore, the minimum
of these cases is 113, which is selected
as the output.
Example 2:
Input:
N = 3
A[] = {15,17,20}
M = 2
Output:32
Explanation: Allocation is done as
{15,17} and {20}Your Task:
You don’t need to read input or print anything. Your task is to complete the function findPages() which takes 2 Integers N, and m and an array A[] of length N as input and returns the expected answer.
Expected Time Complexity: O(NlogN)
Expected Auxilliary Space: O(1)
Constraints:
1 <= N <= 105
1 <= A [ i ] <= 106
1 <= M <= 105
Solution
// { Driver Code Starts
// Initial template for C++
#include<bits/stdc++.h>
using namespace std;
// } Driver Code Ends
//User function template in C++
class Solution
{
public:
//Function to find minimum number of pages.
bool isPossible(int barrier, int A[], int N, int M)
{
int pages=0, students=1 ;
for(int i=0 ; i<N ; i++)
{
if(barrier<A[i]) return false ;
if(pages+A[i]>barrier)
{
students++ ;
pages=0 ;
pages+=A[i] ;
}
else
pages+=A[i] ;
}
return students>M ? false : true ;
}
//Function to find minimum number of pages.
int findPages(int A[], int N, int M)
{
int ans=-1, low=INT_MAX, high=0 ;
for(int i=0 ; i<N ; i++)
low=min(low,A[i]), high+=A[i] ;
while(low<=high)
{
int mid = (low+high)/2 ;
if(isPossible(mid,A,N,M))
{
ans=mid ;
high=mid-1 ;
}
else low=mid+1 ;
}
return ans ;
}
};
// { Driver Code Starts.
int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int A[n];
for(int i=0;i<n;i++){
cin>>A[i];
}
int m;
cin>>m;
Solution ob;
cout << ob.findPages(A, n, m) << endl;
}
return 0;
}
// } Driver Code Ends17. Subarray with given sum
Given an unsorted array A of size N that contains only non-negative integers, find a continuous sub-array which adds to a given number S.
In case of multiple subarrays, return the subarray which comes first on moving from left to right.
Example 1:
Input:
N = 5, S = 12
A[] = {1,2,3,7,5}
Output: 2 4
Explanation: The sum of elements
from 2nd position to 4th position
is 12.Example 2:
Input:
N = 10, S = 15
A[] = {1,2,3,4,5,6,7,8,9,10}
Output: 1 5
Explanation: The sum of elements
from 1st position to 5th position
is 15.
Your Task:
You don’t need to read input or print anything. The task is to complete the function subarraySum() which takes arr, N and S as input parameters and returns an arraylist containing the starting and ending positions of the first such occurring subarray from the left where sum equals to S. The two indexes in the array should be according to 1-based indexing. If no such subarray is found, return an array consisting only one element that is -1.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 105
1 <= Ai <= 109
Solution
// { Driver Code Starts
#include <bits/stdc++.h>
using namespace std;
// } Driver Code Ends
class Solution
{
public:
//Function to find a continuous sub-array which adds up to a given number.
vector<int> subarraySum(int arr[], int n, long long s)
{
// Your code here
vector<int>v;
if(arr[0]==s){
return {1,1};
}
int i=0,j=i+1;
long long sum=0;
sum=arr[i]+arr[j];
while(i<n and j<n){
if(sum==s) return {i+1,j+1};
if(sum>s){
sum-=arr[i];
i++;
}
else{
j++;
sum+=arr[j];
}
}
return {-1};
}
};
// { Driver Code Starts.
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
long long s;
cin>>n>>s;
int arr[n];
const int mx = 1e9;
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
Solution ob;
vector<int>res;
res = ob.subarraySum(arr, n, s);
for(int i = 0;i<res.size();i++)
cout<<res[i]<<" ";
cout<<endl;
}
return 0;
} // } Driver Code Ends18. Median of Two sorted arrays
Given two sorted arrays of sizes N and M respectively. The task is to find the median of the two arrays when they get merged.
If there are even number of elements in the resulting array, find the floor of the average of two medians.
Example 1:
Input:
N = 5, M = 6
arr[] = {1,2,3,4,5}
brr[] = {3,4,5,6,7,8}
Output: 4
Explanation: After merging two arrays,
elements will be as 1 2 3 3 4 4 5 5 6 7 8
So, median is 4.Example 2:
Input:
N = 2, M = 3
arr[] = {1,2}
brr[] = {2,3,4}
Output: 2
Explanation: After merging two arrays,
elements will be as 1 2 2 3 4. So,
median is 2.
Your Task:
You do not need to read input or print anything. Complete findMedian() function which takes the two arrays and n and m as input parameters and returns their median. If there are total even elements, return floor of average of middle two elements.
Expected Time Complexity : O(log(max(m,n)))
Expected Auxilliary Space : O(1)
Constraints:
1 <= N, M <= 106
1 <= arr[i], brr[i] <= 107
Solution
// { Driver Code Starts
//Initial template for C++
#include <bits/stdc++.h>
using namespace std;
// } Driver Code Ends
//User function template for C++
class Solution
{
public:
//Function to find the median of the two arrays when they get merged.
int findMedian(int arr[], int n, int brr[], int m)
{
if(n>m) return findMedian(brr,m,arr,n);//(Imp)
int b = 0, end = n;
while (b <= end)
{
int i1 = (b + end) / 2;
int i2 = (n + m + 1) / 2 - i1;
int min1 = (i1 == n) ? INT32_MAX : arr[i1];
int max1 = (i1 == 0) ? INT32_MIN : arr[i1 - 1];
int min2 = (i2 == m) ? INT32_MAX : brr[i2];
int max2 = (i2 == 0) ? INT32_MIN : brr[i2 - 1];
if (max1 <= min2 && max2 <= min1)
{
if ((n + m) % 2 == 0)
return ((double)max(max1, max2) + min(min1, min2)) / 2;
else
return (double)max(max1, max2);
}
else if (max1 > min2)
{
end = i1 - 1;
}
else
{
b = i1 + 1;
}
}
return 0;
}
};
// { Driver Code Starts.
int main() {
int t;
cin >> t;
while(t--){
int n, m;
cin >> n >> m;
int arr[n];
int brr[m];
for(int i = 0;i<n;i++){
cin >> arr[i];
}
for(int i = 0;i<m;i++){
cin >> brr[i];
}
Solution obj;
if(n < m)
cout << obj.findMedian(arr, n, brr, m) << endl;
else
cout << obj.findMedian(brr, m, arr, n) << endl;
}
} // } Driver Code EndsHappy Learning – If you require any further information, feel free to contact me.
![[Solved] Equally Happy Contest Problem](https://realcoder.techss24.com/wp-content/uploads/2022/06/Solved-Equally-Happy-Contest-Problem-300x200.png)
![[Solved] K-th Symbol in Grammar Contest Problem](https://realcoder.techss24.com/wp-content/uploads/2022/06/Solved-K-th-Symbol-in-Grammar-Contest-Problem-300x200.png)
![[Solved] Greatest English Letter in Upper and Lower Case Contest Problem](https://realcoder.techss24.com/wp-content/uploads/2022/06/Solved-Greatest-English-Letter-in-Upper-and-Lower-Case-Contest-Problem-300x200.png)