Problem Link
Author: Sahil Rajput
Tester: Sahil Rajput
Editorialist: Sahil Rajput
Difficulty
EASY
Prerequisites
Maths
Problem
Given an array of N size with K elements in the array. Task is to find the Minimum and Maximum number of possible good places in the array, A place is called good place when at least one value is already present adjacent to it.
Explanation
The approach for this question is simple calculation with some exceptions. The exceptions are cases in which K = 0 and K = N, in these cases both minimum and maximum number of good places is 0 since there is no inhabitant or vacant index in the array. Calculate the number of places with indices 2, 5, 8 and so on excluding the one with index N if it exists. Number of that places is equal to x = (floor)(N/3) , and if K ≤ x you can occupy some of these places to reach maximum number of good places equal to 2·K. Otherwise, if K> x, assume that place with indices 2, 5, 8 and so on are occupied, so any place has at least one inhabited place adjacent to it. Therefore number of good places for the value is equal to number of vacant places and is equal to n - k.
Time complexity
O(1).
Solution Link