Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.

UPCOMING CHALLENGES:

CURRENT CHALLENGES:

The Doge 2021

PAST CHALLENGES

The Matrix 2021

The OLX Group challenge

Silver 2020

Palladium 2020

Rhodium 2019

Ruthenium 2019

Technetium 2019

Molybdenum 2019

Niobium 2019

Zirconium 2019

Yttrium 2019

Strontium 2019

Rubidium 2018

Arsenicum 2018

Krypton 2018

Bromum 2018

Future Mobility

Grand Challenge

Digital Gold

Selenium 2018

Germanium 2018

Gallium 2018

Zinc 2018

Cuprum 2018

Cutting Complexity

Nickel 2018

Cobaltum 2018

Ferrum 2018

Manganum 2017

Chromium 2017

Vanadium 2016

Titanium 2016

Scandium 2016

Calcium 2015

Kalium 2015

Argon 2015

Chlorum 2014

Sulphur 2014

Phosphorus 2014

Silicium 2014

Aluminium 2014

Magnesium 2014

Natrium 2014

Neon 2014

Fluorum 2014

Oxygenium 2014

Nitrogenium 2013

Carbo 2013

Boron 2013

Beryllium 2013

Lithium 2013

Helium 2013

Hydrogenium 2013

Omega 2013

Psi 2012

Chi 2012

Phi 2012

Upsilon 2012

Tau 2012

Sigma 2012

Rho 2012

Pi 2012

Omicron 2012

Xi 2012

Nu 2011

Mu 2011

Lambda 2011

Kappa 2011

Iota 2011

Theta 2011

Eta 2011

Zeta 2011

Epsilon 2011

Delta 2011

Gamma 2011

Beta 2010

Alpha 2010

Find a longest slice of a binary array that can be split into two parts: in the left part, 0 should be the leader; in the right part, 1 should be the leader.

You want to spend your next vacation in Poland. Despite its not being a very big country, Poland has a highly diverse natural environment ranging from the Baltic Sea in the north to the Tatra Mountains in the south. As you enjoy swimming in the sea as well as trekking up mountains, you would like to spend some time in both of those locations. However, the weather in Poland can sometimes be very capricious, so you also need to take that into account when planning your vacation.

In the summer you are free for N consecutive days. You can start and finish your vacation on any of these days. You want to spend the first part of your vacation at the seaside and the remaining part in the mountains. These parts can each be of any positive length, and you want to maximize the total length of the vacation.

You have obtained a weather forecast for all N days when you are free. By curious coincidence, the weather on every day is expected to be either perfect for spending the day at the seaside but not in the mountains, or vice versa (perfect for trekking but not for swimming). Obviously, you want the best possible weather during each part of your vacation, so you require the weather to be perfect for swimming for more than half of the days in the first part of your vacation, and perfect for trekking for more than half of the days in the second part of your vacation.

The weather forecast is described in an array A: for each K (0 ≤ K < N), A[K] is equal to 0 if the weather during day K favors the seaside, or 1 if the weather during that day favors the mountains.

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A of N integers, returns the length of the longest vacation consistent with your requirements.

For example, consider array A such that:

You are free for eight days. The weather during days 2, 4 and 5 will be better for swimming, and better for trekking during the remaining days. You can start your vacation on day 1, spend five days at the seaside (three days will have perfect weather, which is more than half) and then spend two days in the mountains (both days will have perfect weather). That results in a vacation length of seven days, which is the longest possible vacation that meets your criteria, so the function should return 7.

For array A such that:

there is no vacation that satisfies your requirements, so the function should return 0.

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [2..100,000];
- each element of array A is an integer that can have one of the following values: 0, 1.

Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.