There is a road consisting of N segments, numbered from 0 to N-1 (JavaScript Solution)- Interviews Questions

There is a road consisting of N segments, numbered from 0 to N-1, represented by a string S. Segment S[K] of the road may contain a pothole, denoted by a single uppercase "X" character, or maybe a good segment without any potholes, denoted by a single dot, ".".

For example, the string ".X..X" means that there are two potholes in total in the road: one is located in segment S[1] and one in segment S[4]. All other segments are good.

The road fixing machine can patch over three consecutive segments at once with asphalt and repair all the potholes located within each of these segments. Good or already repaired segments remain good after patching them.

Your task is to compute the minimum number of patches required to repair all the potholes in the road.

Write a function: 

function solution(S);

that, given a string S of length N, returns the minimum number of patches required to repair all the potholes.

{getToc} $title={Table of Contents}

Examples:

  1. Given S = ".X..X", your function should return 2. The road fixing machine could patch, for example, segments 0-2 and 2-4. 
  2. Given S = "X.XXXXX.X.", your function should return 3. The road fixing machine could patch, for example, segments 0-2, 3-5, and 6-8.
  3. Given S = "XX.XXX..", your function should return 2. The road fixing machine could patch, for example, segments 0-2 and 3-5.
  4. Given S = "XXXX", your function should return 2. The road fixing machine could patch, for example, segments 0-2 and 1-3.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [3..100,000];

string S consists only of the characters "." and/or "X". 

Solution (JavaScript):

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(S) {
    var i;
    var k;
    var out=0;
    var j=parseInt(S.length/3);
    
    for (i = 0; i <s; j; i++) {
        var res=S.slice(3*i,3+3*i);
        for (k=0;k <s; 3;k++){
            if(res[k]=="X"){
                out=out+1;
                break;
            }
        }
}

   var l=S.length-3*j
   if(l>0){
       if(S[3*j]=="X"){
           out=out+1;
           }
       else if(S[3*j+1]=="X"){
           out=out+1;
           }
   }
   console.log(out);
   return out;
}
solution(".X..X");

Solution (C++ Programming Language):

#include<iostream>
using namespace std;

int solution(string str)
{

int patchesCount=0;
for(int i=0;i<str.size();i++) // run upto the number of character inside str.
{
if(str[i]=='.') continue; // if road is ok then continue to run. no need to patch
else{
patchesCount++;
if(str[i+1]=='X' || str[i+2]=='X') i+=2; // if there is any consecutive pothole after any hole then it will be covered in a single patch.
}
}
return patchesCount;
}

int main()
{
string s;
cout<<"Enter the condition of road(combination of 'X' and '.') : ";
cin>>s; // Taken input in s string
cout<<solution(s)<<" patches required to repair the road."<<endl; // sending the string s to get the number of patches.

return 0;
}

Sharecodepoint

Sharecodepoint is the junction where every essential thing is shared for college students in the well-defined packets of codes. We are focused on providing you the best material package like Question papers, MCQ'S, and one NIGHT STUDY MATERIAL. facebook twitter youtube instagram

Post a Comment

Previous Post Next Post

Contact Form