Contest Link : www.codechef.com/CCB12020
Editorialist Username : thesparkvision
Problem Code : FAULTCB
DIFFICULTY :
Easy-Medium
PREREQUISITES:
PROBLEM:
You are given an array A of size N and 2 integers D and C
-
Search whether D is present in Array and if present, replace it with C
-
Find the count of the third maximum value of Array A after task 1 is complete
-
Print the final array in a sorted manner and the count of third maximum value
Time Complexity:
O ( nlogn ) in worst case if good sorting algorithm is used. Else O(n2)
QUICK EXPLANATION (Approach 1):
Firstly, check whether the value D is present in array A using linear search or not and if present gets its position and using it replace D with C. Then sort the array in ascending order using any sorting algorithm. Then, maintain another array B=A. Remove the maximum value occurrences and second maximum value occurrences out of B. Then find the maximum value again and find how many times it is occurring.
EXPLANATION (Approach 2):
Firstly take input N, A, C and D. Then find by running a loop on array A if any element of A is equal to D. If any element is equal, you will get the position of that element. Using that position, replace D with C. Now, Sort the array using any sorting algorithm like bubble sort or quick sort or the built-in sorting functions of C++, Python, etc. Then, find the maximum value of the array. After that, search where the first occurrence of this maximum value max is, say this is pos.
Now, you again find the maximum value in the array from 0 to pos-1(because we do not have to include the maximum element). This will be the second-highest element, say it is second_max. Now, again find the first occurrence of second_max in the array using linear search, say it is at second_pos.
Now, we only have to find the maximum value in the array from 0 to second_pos-1. This will give us the third-highest value which we needed. Find the maximum value and store it in third_max. Now, again count how many times third_max occurs in an array A, and store it in the variable count.
Print the sorted array A and the value count in separate lines.
EXPLANATION (Approach 3):
Firstly take input N, A, C and D. Then find by running a loop on array A if any element of A is equal to D. If any element is equal, you will get the position of that element. Using that position, replace D with C. Now, Sort the array using any sorting algorithm like bubble sort or quick sort or the built-in sorting functions of C++, Python, etc.
Maintain some variables. Set max equal to the last element. Since the array is sorted, the last element is the maximum value. Set second_max and third_max to -1 which means they are not known yet. Set count=0
Now, we will run the loop from the last since we want maximum values. We will check each element from the back and try to find an element which does not equal to max since there can be multiple occurrences of max. When we find such an element, we have got second_max. Now, our value will not be equal to max. We will check whether second_max is equal to -1 or not. If it is not equal to -1, we will check if any element is not equal to second_max so that we can find third_max. We will get third_max. We will increase count to 1. Now we will keep on checking each element. If we get value equal to third_max, we will increase count by 1.
And in last, we will print the array A and count variable in separate lines.
PseudoCode (Approach 2):
Input(N)
Input(A)
Input(D and C)
p=-1
For every element in A:
If current element is equal to D:
p=position of current element
A[p]=C
Stop Searching
Else:
then check next element
Sort(A)
pos=0
max=-9999
For every element in A:
if value of current element >max:
max=value of current element
For every element in A:
if value of the current element is equal to max:
pos=position of current element
Stop searching
else:
continue checking next element
second_pos=0
second_max=-9999
For every element in A before position pos:
if value of current element >second_max:
second_max=value of current element
For every element in A before position pos:
if value of current element is equal to second_max:
second_pos=position of second_max
Stop searching
else:
continue checking next element
third_max=-9999
For every element in A before position second_pos:
if value of current element >third_max:
third_max=value of current element
count=0
For every element in A:
if value of element equal to third_max:
Increase value of count by 1
Print(A)
Print(count)
Solutions:
C Solution (Approach 3)
#include <stdio.h>
void sort(int arr[],int n)
{
for(int i=0;i<n-1;i++)
for(int j=i;j<n;j++)
if(arr[i]>arr[j]){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
int main()
{
//Input
int i,N,D,C,A[100];
scanf("%d",&N);
for(i=0;i<N;i++)
scanf("%d",&A[i]);
scanf("%d %d",&D,&C);
//searching and updating
int pos=0;
for(i=0;i<N;i++)
if (A[i]==D)
A[i]=C;
break;
//Sorting the array using user-defined sort function
sort(arr,n);
//Finding third maximum value count
int max=arr[n-1],second_max=-1,third_max=-1,count=0;
for(i=N-2;i>=0;i--)
if(A[i]!=max && second_max==-1)
secondmax=A[i];
else if(A[i]!=second_max && third_max==-1)
{third_max=A[i];
count++;}
else if(A[i]==third_max)
count++;
//Output
for(i=0;i<N;i++)
printf("%d ",A[i]);
printf("\n%d",count);
return 0;
}
C++ Solution(Approach 3 but with binary search)
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
void sort(int arr[],int n)
{
for(int i=0;i<n-1;i++)
for(int j=i;j<n;j++)
if(arr[i]>arr[j])
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
int binary_search(int arr[],int l,int r,int d)
{
if(l<=r)
{
int mid=(l+r)/2;
if (arr[mid]==d)
return mid;
else if(arr[mid]>d)
return binary_search(arr,l,mid-1,d);
else
return binary_search(arr,mid+1,r,d);
}
else
return -1;
}
int main()
{
//Input
int i,n,d,c,arr[100];
cin>>n;
for(i=0;i<n;i++)
cin>>arr[i];
cin>>d>>c;
//Sorting, searching and updating and again sorting
sort(arr,n);
int pos=binary_search(arr,0,n-1,d);
if(pos!=-1)
arr[pos]=c;
sort(arr,n);
//Finding third maximum value count
int max=arr[n-1],secondmax=-1,thirdmax=-1,count=0;
for(i=n-2;i>=0;i--)
if(arr[i]!=max && secondmax==-1)
secondmax=arr[i];
else if(arr[i]!=secondmax && thirdmax==-1)
{thirdmax=arr[i];
count++;}
else if(arr[i]==thirdmax)
count++;
//Output
for(i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl<<count;
return 0;
}
Java Solution (Approach 3)
import java.util.Scanner;
import java.util.Arrays;
public class Main {
//binary search auxiliary function
static int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
//main function
public static void main(String[] args) {
//Input
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
StringBuffer ans = new StringBuffer();
for(int i=0;i<n;i++)
arr[i] = sc.nextInt();
int d=sc.nextInt();
int c=sc.nextInt();
//Sorting,searching,updating and sorting
Arrays.sort(arr);
int pos=binarySearch(arr,0,n-1,d);
if(pos!=-1)
arr[pos]=c;
Arrays.sort(arr);
//Finding third max
int max=arr[n-1],secondmax=-1,thirdmax=-1,count=0;
for(int i=n-2;i>=0;i--)
if(arr[i]!=max && secondmax==-1)
secondmax=arr[i];
else if(arr[i]!=secondmax && thirdmax==-1)
{thirdmax=arr[i];
count++;}
else if(arr[i]==thirdmax)
count++;
//Output
for(int i =0;i<n;i++)
{
System.out.print(""+arr[i]+" ");
}
System.out.println("");
System.out.print(""+count);
}
}
Python Solution(Approach 1)
#Input
n=int(input())
a=list(map(int,input().split()))
d,c=map(int,input().split())
#Sorting
a.sort()
#Searching D in A and if present updating with C
try:
pos=a.index(d)
if pos!=-1:
a[pos]=c
except:
pass
#Again Sorting
a.sort()
#Finding max and its position in A
m1=max(a)
ind=a.index(m1)
#Finding second_max and its position in A
m2=max(a[:ind])
ind=a.index(m2)
#Finding third_max in A
m3=max(a[:ind])
#Printing array with space separated values
print(*a,sep=" ")
#Finding count of third_max in A and printing it
print(a.count(m3))
C++ Solution using vectors and in-built functions(Approach 3)
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
//Input
int i,n,d,c,input;
vector <int> arr;
cin>>n;
for(i=0;i<n;i++)
{
cin>>input;
arr.push_back(input);
}
cin>>d>>c;
//Sorting ,searching and updating and again sorting
sort(arr.begin(), arr.end());
int pos= lower_bound(arr.begin(), arr.end(), d) - arr.begin();
if(pos!=-1)
arr[pos]=c;
sort(arr.begin(), arr.end());
//Finding third maximum value count
int max=arr[n-1],secondmax=-1,thirdmax=-1,count=0;
for(i=n-2;i>=0;i--)
if(arr[i]!=max && secondmax==-1)
secondmax=arr[i];
else if(arr[i]!=secondmax && thirdmax==-1)
{thirdmax=arr[i];
count++;}
else if(arr[i]==thirdmax)
count++;
//Output
for(i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl<<count;
return 0;
}