Minimum Number Of Lamps — Asked in Adobe Interview

Problem Statement :

You are given a string ‘S’ containing dots(.) and asterisks(*) only, where the dot represents free spaces, and the asterisk denotes lamps. A lamp can lighten up its own cell as well as its immediate neighboring cells. You need to determine the minimum number of extra lamps that have to be installed at some free spaces in the string so that the whole string will be illuminated i.e. all the indices of the string can have access to the light of some lamp.

Sample Input:

 *.*..

Sample Output:

1

Explanation for Test Case :

For the given test case, indices from 1 to 4 will be illuminated. We only need to install one lamp at index 5. Hence the answer is 1.

Approach :

Greedy algorithm

  • The first thing to note is that for every three continuous dots, we will require one lamp. So if we have ‘K’ continuous dots, we will need exactly ‘K’/3 lamps if ‘K’ is a multiple of 3. When ‘K’ is not a multiple of 3, we will require ceil(‘K’ / 3) lamps because if we take the floor(‘K’ / 3) there will be 1 or 2 extra spaces that will not be covered, for that we will require one extra lamp. Hence in total, we need ceil(‘K’ / 3) lamps.
  • Firstly we need to preprocess the string as follows:
  • If you encounter an asterisk at index ‘I’, then mark its neighboring cells, ‘I’.e. ‘I’-1 and ‘I’ + 1 also by an asterisk, provided the adjacent cells exist. This is done because there is no need to install lamps on these cells.
  • Now the only thing left is to count the number of empty dots and apply the formula given in the first point.
  • After preprocessing, let ‘ANS’ = 0 and count = 0. Start traversing the string from ‘I’ = 0 to ’N’ — 1 and do the following:
  • If S[i] = ‘*’, then ‘ANS’ = ‘ANS’ + ceil(‘COUNT’/ 3) and ‘COUNT’ = 0. After finding a star, the number of dots in the current segment will become zero.
  • Else if ‘S’[‘I’] = ‘.’, then ‘COUNT’ = ‘COUNT’ + 1.

Time Complexity : O(N)
Space Complexity : O(1)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.

--

--

--

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Exploratory reflection on design ethics

How To Replace A Shower Head Step By Step Process Illustrated Process

Role shifting as a designer

Top 4 skills Librarians have to navigate digital disruption

UX for an early-stage Startup

Cultivando Bienestar; CBD Responsive Website

Peacock Style Silver Oxidised Jhumki for Girls

Lightspeed prototyping and iterating iterated iterations (3x a day): the vaccination campaign in…

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Placewit

Placewit

Upskilling students for tech placements!

More from Medium

One Mile on the globe Puzzle

Leetcode Q84. Largest Rectangle in Histogram

Do not ask this question in Coding Interview

Longest Increasing Subsequence Coding Question