304 North Cardinal St.
Dorchester Center, MA 02124

# Little Elephant and Median CodeChef Solution

## Little Elephant and Median CodeChef Solution in C++14

``````#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>

#include <cassert>
#include <limits>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define each(it,o) for(auto it= (o).begin(); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define inrep int t;cin>>t; while(t--)
using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii > vpii;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef vector<pll > vpll;
typedef vector<string> vs;
typedef long double ld;

template<typename T> ostream& operator<< ( ostream &o,vector<T> v ) {
if ( v.size() >0 )
o<<v[0];
for ( unsigned   i=1; i<v.size(); i++ )
o<<" "<<v[i];
return o<<endl;
}
template<typename U,typename V> ostream& operator<< ( ostream &o,pair<U,V> p ) {
return o<<"("<<p.first<<", "<<p.second<<") ";
}
template<typename T> istream& operator>> ( istream &in,vector<T> &v ) {

for ( unsigned   i=0; i<v.size(); i++ )
in>>v[i];
return in;
}
void apply ( int ma,int n, vi &vals ) {
int lst=0;
//     cout<<ma<<endl;
rep ( i,n ) {
bool cur=ma & ( 1<<i );
if ( !lst ) {
int cnt1=cur;
int cnt0=!cur;
int ma2=ma | ( 1<<i );
reu ( j,i+1,n ) {
if ( ma& ( 1<<j ) ) cnt1++;
else cnt0++;
ma2=ma2| ( 1<<j );
if ( cnt0 &&  cnt1>=cnt0 ) {
//                     cout<<mp ( i,j ) <<": "<<ma2<<endl;
vals.push_back ( ma2 );
}
}
}
lst=cur;
}
}
int main() {
ios_base::sync_with_stdio ( false );
inrep {
int n;
cin>>n;
vi a ( n );
cin>>a;
int amax=*max_element ( all ( a ) );
rep ( i,n ) if ( a[i]==amax ) mask|=1<<i;
int cnt=__builtin_popcount ( mask );
if ( cnt==n ) {
cout<<0<<'\n';
continue;

}
int d=0;
int fnd=0;
while ( 1 ) {
vi nst;
for ( int j: st ) {
int cnt=__builtin_popcount ( j );
if ( cnt>=n-cnt ) {
fnd=d+1;
break;
}

apply ( j,n,nst );
}
//             cout<<nst<<endl;
if ( fnd ) break;
swap ( st,nst );
d++;
}
cout<<fnd<<'\n';

}
}``````

## Little Elephant and Median CodeChef Solution in C

``````#include<stdio.h>
#include<stdlib.h>
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
int a[32],b[32];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
int i;int max_num=-1;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
max_num=max(max_num,a[i]);

}
int cnt=0,cnt1=0;
for(i=0;i<n;i++)
b[i]=a[n-(i+1)];
while(1)
{
int l,h,mmax=0,j,k;
int i;
for(i=0;i<n;i++)
if(a[i]!=max_num)
break;
if(i==n) break;
cnt++;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
int c=0;
for(k=i;k<=j;k++)
{
if(a[k]==max_num)
c++;
}
int num_elements=j-i+1;
if(c>=(num_elements+1)/2 && num_elements>mmax)
{
mmax=num_elements;
l=i;
h=j;
}
}
}
// printf("%d %d\n",l,h);
for(i=l;i<=h;i++)
a[i]=max_num;
}

while(1)
{
int l,h,mmax=0,j,k;
int i;
for(i=0;i<n;i++)
if(b[i]!=max_num)
break;
if(i==n) break;
cnt1++;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
int c=0;
for(k=i;k<=j;k++)
{
if(b[k]==max_num)
c++;
}
int num_elements=j-i+1;
if(c>=(num_elements+1)/2 && num_elements>mmax)
{
mmax=num_elements;
l=i;
h=j;
}
}
}
// printf("%d %d\n",l,h);
for(i=l;i<=h;i++)
b[i]=max_num;
}
printf("%d\n",min(cnt,cnt1));
}
}
``````

## Little Elephant and Median CodeChef Solution in JAVA

``````import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.InputMismatchException;
import java.util.PriorityQueue;

public class Main {
static class State implements Comparable<State>{
int done = 0, max = 0, it = 0;
@Override
public int compareTo(State o) {
if(this.it<o.it || (this.it==o.it && this.max>=o.max))
return -1;
return 1;
}
}

public static void main(String[] args) throws Exception {
OutputWriter out = new OutputWriter(System.out);
while(t --> 0){
int n = in.readInt();
int max = 0;
int[] nums = new int[n];
for(int i=0;i<n;i++){
if(nums[i] > max)
max = nums[i];
}
int start=-1,end=-1;
State state = new State();
for(int i=0;i<n;i++){
if(nums[i]==max){
state.done |= 1<<i;
state.max++;
if(start==-1)
start=i;
end = i;
}
}
if((end-start)<state.max*2){
while(state.max < n){
state.max*=2;
state.it++;
}
}else{
PriorityQueue<State> pq = new PriorityQueue<State>();
state.it++;
state.max*=2;
while(state.max < n){
int maxtot = state.max;
boolean isDone=false;
while(!isDone){
for(int i=0;i<=n-maxtot;i++){
int subtot = 0;
for(int j=0;j<maxtot;j++){
if((state.done & (1<<(i+j))) > 0)
subtot++;
else
subtot--;
}
if(subtot==0){
if(maxtot%2>0)
throw new RuntimeException("o_O maxtot div by 2");
isDone=true;
State next = new State();
next.max = state.max+maxtot;
next.it = state.it+1;
next.done = state.done;
for(int j=i;j<i+maxtot;j++){
next.done |= 1<<j;
}
}
}
maxtot=(maxtot==2?1:maxtot-2);
}
state = pq.poll();
}
}
out.printLine(state.it);
}
out.close();
}

static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;

public InputReader(InputStream stream) {
this.stream = stream;
}

public int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}

public int readInt() {
int c = read();
while (isSpaceChar(c))
int sgn = 1;
if (c == '-') {
sgn = -1;
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
} while (!isSpaceChar(c));
return res * sgn;
}

public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
}

static class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}

public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}

public void print(Object... objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0)
writer.print(' ');
writer.print(objects[i]);
}
}
public void printLine(Object... objects) {print(objects);writer.println();}
public void close() {writer.close();}
}
}``````

## Little Elephant and Median CodeChef Solution in PYTH

``````#!/usr/bin/env python

def process(N, A):
C = 0
M = max(A)
w = N
while w and A.count(M) != N:
o = 0
P = []
while o+w <= N:
if A[o:o+w].count(M) >= w / 2.:
Anew = list(A)
for k in xrange(o,o+w): Anew[k] = M
P.append(Anew)
o += 1
if P:
return 1 + min(map(lambda p: process(N, p), P))
w -= 1
return C

def main():
T = int(raw_input().strip())
for t in xrange(T):
N = int(raw_input().strip())
A = map(int, raw_input().strip().split()[:N])
print process(N, A)

main()
``````

## Little Elephant and Median CodeChef Solution in C#

``````using System;
using System.Collections.Generic;

namespace NewFindMedianProgram
{
public class Program
{
public static void Main()
{
var noOfTestCases = Convert.ToInt32(Console.ReadLine());
for (var i = 0; i < noOfTestCases; i++)
{
var listOfMaxNumberIndex = new List<int>();
var noOfIntInArray = Convert.ToInt32(Console.ReadLine());
var maxNumber = 0;
if (readLine == null) continue;
var inputArray = readLine.Split(' ');
var noOfOperation = 0;
for (var j = 0; j < noOfIntInArray; j++)
{
var number = Convert.ToInt32(inputArray[j]);
if (number < maxNumber)
continue;
if (number == maxNumber)
{
continue;
}
if (number > maxNumber)
{
maxNumber = number;
listOfMaxNumberIndex = new List<int> {j};
}
}

while (listOfMaxNumberIndex.Count < noOfIntInArray)
{
noOfOperation++;
listOfMaxNumberIndex.Sort();
CalculateAndUpdateMaxNumberIndex(listOfMaxNumberIndex, noOfIntInArray);
}
Console.WriteLine(noOfOperation);
}
}

private static void CalculateAndUpdateMaxNumberIndex(List<int> listOfMaxNumberIndex, int noOfIntInArray)
{
var countOfMaxElements = listOfMaxNumberIndex.Count;
var medianCheck = noOfIntInArray/2 + 1;
var median = noOfIntInArray - medianCheck + 1;
var noOfMaxElementsIncluded = 0;
var listOfCompatibleIndex = new List<IndexList>();
if(countOfMaxElements >= median)
{
for (var i = 0; i < noOfIntInArray; i++)
{
if(!listOfMaxNumberIndex.Contains(i))
}
return;
}
for (var i = 0; i < countOfMaxElements; i++)
{
for (var j = countOfMaxElements - 1; j >= i; j--)
{
var noOfElementsIncluded = listOfMaxNumberIndex[j] - listOfMaxNumberIndex[i] + 1;
var noOfMaxElements = j - i + 1;
var elementThatCanBeIncluded = noOfMaxElements*2;
//var medianOfIncludedCheck = noOfElementsIncluded/2 + 1;
//var medianOfIncluded = noOfElementsIncluded - medianOfIncludedCheck;
if(elementThatCanBeIncluded >= noOfElementsIncluded)
{
if (noOfMaxElementsIncluded > elementThatCanBeIncluded)
continue;
var currentIndexListElement = new IndexList
{
startIndex = listOfMaxNumberIndex[i],
endIndex = listOfMaxNumberIndex[j],
diffToLeft = -1,
diffToRight = -1,
noOfMaximumElements = noOfMaxElements
};
if (i - 1 >= 0)
{
currentIndexListElement.diffToLeft = listOfMaxNumberIndex[i] - listOfMaxNumberIndex[i - 1];
}
if (j + 1 < countOfMaxElements)
{
currentIndexListElement.diffToRight = listOfMaxNumberIndex[j + 1] -
listOfMaxNumberIndex[j];
}
if (elementThatCanBeIncluded > noOfMaxElementsIncluded)
{
noOfMaxElementsIncluded = elementThatCanBeIncluded;
listOfCompatibleIndex = new List<IndexList>();
}
}

}
}
var left = false;
var finalIndexListToUse = new IndexList();
var minDiffOfAll = noOfIntInArray;
if (listOfCompatibleIndex.Count == 1)
ReplaceList(noOfIntInArray, listOfCompatibleIndex[0], listOfMaxNumberIndex);
else
{
foreach (var indexList in listOfCompatibleIndex)
{
var minDiffForThisIndexList = noOfIntInArray;
var leftForThisIndexList = false;
if (indexList.diffToLeft != -1)
{
minDiffForThisIndexList = indexList.diffToLeft;
leftForThisIndexList = true;
}
if (indexList.diffToRight != -1 && indexList.diffToRight < minDiffForThisIndexList)
{
minDiffForThisIndexList = indexList.diffToRight;
}
if(minDiffForThisIndexList < minDiffOfAll)
{
minDiffOfAll = minDiffForThisIndexList;
left = leftForThisIndexList;
finalIndexListToUse = indexList;
}
}
ReplaceList(noOfIntInArray, finalIndexListToUse, listOfMaxNumberIndex, left);
}
}

private static void ReplaceList(int noOfIntInArray, IndexList indexList, List<int> listOfMaxNumberIndex, bool left)
{
var noOfMaxElements = indexList.noOfMaximumElements;
var maxNoOfElementsToConverted = noOfMaxElements * 2;
if(maxNoOfElementsToConverted >= noOfIntInArray)
{
for (var i = 0; i < noOfIntInArray; i++)
{
if(!listOfMaxNumberIndex.Contains(i))
}
return;
}
if(!left)
{
for (var i = 0; i < maxNoOfElementsToConverted; i++)
{
if(!listOfMaxNumberIndex.Contains(indexList.startIndex + i))
}
return;
}
for (var i = maxNoOfElementsToConverted; i > 0; i--)
{
if(!listOfMaxNumberIndex.Contains(indexList.endIndex - i))
}
}

private static void ReplaceList(int noOfIntInArray, IndexList indexList, List<int> listOfMaxNumberIndex)
{
var noOfMaxElements = indexList.noOfMaximumElements;
var maxNoOfElementsToConverted = noOfMaxElements * 2;
if (maxNoOfElementsToConverted >= noOfIntInArray)
{
for (var i = 0; i < noOfIntInArray; i++)
{
if (!listOfMaxNumberIndex.Contains(i))
}
return;
}
var left = false;
var startIndex = indexList.startIndex;
var endIndex = indexList.endIndex;
var diffRight = noOfIntInArray - endIndex - 1;
if (indexList.diffToLeft == -1 && indexList.diffToRight == -1)
{
left = startIndex > diffRight;
}
else
{
var minDiffForThisIndexList = 0;
var leftForThisIndexList = false;
if (indexList.diffToLeft != -1)
{
minDiffForThisIndexList = indexList.diffToLeft;
leftForThisIndexList = true;
}
if (indexList.diffToRight != -1 && indexList.diffToRight < minDiffForThisIndexList)
{
leftForThisIndexList = false;
}
left = leftForThisIndexList;
}
if(left)
{
if (endIndex - maxNoOfElementsToConverted < 0)
{
for (var i = 0; i < maxNoOfElementsToConverted; i++)
{
if (!listOfMaxNumberIndex.Contains(i))
}
}
else
{
for (var i = 0; i < maxNoOfElementsToConverted; i++)
{
if(!listOfMaxNumberIndex.Contains(endIndex - i))
}
}
}
else
{
if (startIndex + maxNoOfElementsToConverted > noOfIntInArray - 1)
{
for (var i = 0; i < maxNoOfElementsToConverted; i++)
{
if (!listOfMaxNumberIndex.Contains(noOfIntInArray- 1 - i))
listOfMaxNumberIndex.Add(noOfIntInArray - i - 1);
}
}
else
{
for (var i = 0; i < maxNoOfElementsToConverted; i++)
{
if (!listOfMaxNumberIndex.Contains(startIndex + i))
}
}
}
}

public class IndexList
{
public int startIndex;
public int endIndex;
public int diffToLeft = -1;
public int diffToRight = -1;
public int noOfMaximumElements;
}
}
}``````

## Little Elephant and Median CodeChef Solution in GO

``````package main

import (
"bufio"
"bytes"
"fmt"
"os"
)

func main() {

var buf bytes.Buffer

for tc > 0 {
tc--
res := solve(n, A)
buf.WriteString(fmt.Sprintf("%d\n", res))
}

fmt.Print(buf.String())
}

func readInt(bytes []byte, from int, val *int) int {
i := from
sign := 1
if bytes[i] == '-' {
sign = -1
i++
}
tmp := 0
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}

return
}

a, b = res[0], res[1]
return
}

func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
a, b, c = res[0], res[1], res[2]
return
}

res := make([]int, n)
x := 0
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
x = readInt(bs, x, &res[i])
}
return res
}

func readUint64(bytes []byte, from int, val *uint64) int {
i := from

var tmp uint64
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + uint64(bytes[i]-'0')
i++
}
*val = tmp

return i
}
func solve(n int, A []int) int {

mem := make(map[int]int)

var dfs func(mask int) int

dfs = func(mask int) int {
var c1, c0 int
for i := 0; i < n; i++ {
if mask&(1<<uint(i)) > 0 {
c1++
} else {
c0++
}
}
if c0 == 0 {
return 0
}
if c1 >= c0 {
return 1
}
if v, found := mem[mask]; found {
return v
}
var res int = n
for i := 0; i < n; i++ {
var a, b int
to := -1
for j := i; j < n; j++ {
if mask&(1<<uint(j)) > 0 {
a++
} else {
b++
next |= 1 << uint(j)
}
if a >= b && next != mask {
to = next
}
}
if to > 0 {
res = min(res, dfs(to)+1)
}
}
}

mx := A[0]
for i := 1; i < n; i++ {
mx = max(mx, A[i])
}

for i := 0; i < n; i++ {
if A[i] == mx {
mask |= 1 << uint(i)
}
}

}

func min(a, b int) int {
if a <= b {
return a
}
return b
}

func max(a, b int) int {
if a >= b {
return a
}
return b
}``````
##### Little Elephant and Median CodeChef Solution Review:

In our experience, we suggest you solve this Little Elephant and Median CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Little Elephant and Median CodeChef Solution.

Find on CodeChef

##### Conclusion:

I hope this Little Elephant and Median CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!