Chef and Numbers Codechef Solution: Chef has NN dishes of different types arranged in a row: A1,A2,…,ANA1,A2,…,AN, where AiAi denotes the type of the ithith dish. He wants to choose as many dishes as possible from the given list but while satisfying two conditions:
- He can choose only one type of dish.
- No two chosen dishes should be adjacent to each other.
Chef wants to know which type of dish he should choose from, so that he can pick the maximum number of dishes.
Example:
Given NN=99 and AA=[1,2,2,1,2,1,1,1,1][1,2,2,1,2,1,1,1,1].
For type 1, Chef can choose at most four dishes. One of the ways to choose four dishes of type 1 is A1A1, A4A4, A7A7 and A9A9.
For type 2, Chef can choose at most two dishes. One way is to choose A3A3 and A5A5.
So in this case, Chef should go for type 1, in which he can pick more dishes.
Input:
- The first line contains TT, the number of test cases. Then the test cases follow.
- For each test case, the first line contains a single integer NN.
- The second line contains NN integers A1,A2,…,ANA1,A2,…,AN.
Output:
For each test case, print a single line containing one integer ― the type of the dish that Chef should choose from. If there are multiple answers, print the smallest one.
Constraints
- 1≤T≤1031≤T≤103
- 1≤N≤1031≤N≤103
- 1≤Ai≤1031≤Ai≤103
- Sum of NN over all test cases doesn’t exceed 104104
Sample Input:
3 5 1 2 2 1 2 6 1 1 1 1 1 1 8 1 2 2 2 3 4 2 1
Sample Output:
1 1 2
Explanation:
Test case 1:
For both type 1 and type 2, Chef can pick at most two dishes. In the case of multiple answers, we pick the smallest one. Hence the answer will be 11.
Test case 2:
There are only dishes of type 1. So the answer is 11.
Test case 3:
For type 1, Chef can choose at most two dishes. For type 2, he can choose three dishes. For type 3 and type 4, Chef can choose the only dish available. Hence the maximum is in type 2 and so the answer is 22.
Chef and Numbers- CodeChef Solution in JAVA
import java.util.*;
import java.lang.*;
import java.io.*;
class chefnumber
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-->0){
int n=sc.nextInt();
int arr[]=new int[n];
int num=0,len=0, c=0;
for(int i=0;i<n;i++){
arr[i]=sc.nextInt();
}
for(int i=0;i<n;i++){
int count=0;
for(int j=i;j<n;){
if(arr[i]==arr[j]){
count++;
num=arr[i];
j=j+2;}
else{
j++;
}
}
if(len<count){
len=count;
c=num;
}
else if(len==count && c>num){
c=num;
}
}
System.out.println(c);
}
}
}
Chef and Numbers – CodeChef Solution in CPP
#include<bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define SUBL freopen("input.txt", "r", stdin);freopen("saini.txt", "w", stdout)
#define int long long
using namespace std;
int solve(){
int n;cin>>n;
vector<int>a(n);
vector<int>map[1001];
for(int i=0;i<n;i++){
cin>>a[i];
map[a[i]].pb(i+1);
}
int ans=-1,ma=0;
for(int i=1;i<=1000;i++){
if(map[i].size()==0)
continue;
int count=0,in=-1;
for(int j:map[i]){
if(in<j){
count++;
in=j+1;
}
}
if(ma<count){
ma=count;
ans=i;
}
}
return ans;
}
int32_t main()
{
int t;cin>>t;
while(t--)
cout<<solve()<<"\n";
}
Chef and Numbers-CodeChef Solution in Python
num = int(input())
for i in range(num):
count=0
n = int(input())
ls=list(map(int,input().split()))
d=[]
for t in range(0,n-1):
if ls[t]==0:
continue
elif ls[t]==ls[t+1]:
ls[t+1]=0
for m in ls:
if m!=0:
d.append(m)
d.sort()
print(max(d,key=d.count))Disclaimer: The above Problem(Chef and Numbers) is generated by CodeChef but the solution is provided by Chase2learn.This tutorial is only for Educational and Learning purpose.
