Skip to main content

HackerRank Java Coding Questions and Answers - Minimum streets lights

HackerRank  Java  Coding  Questions  and  Answers

Minimum streets lights

Problem Statement -: 

Street Lights are installed at every position along a 1-D road of length n. Locations[] (an array) represents the coverage limit of these lights. The ith light has a coverage limit of locations[i] that can range from the position max((i – locations[i]), 1) to min((i + locations[i]), n ) (Closed intervals). Initially all the lights are switched off. Find the minimum number of fountains that must be switched on to cover the road.

Example

n = 3

locations[] = {0, 2, 13}then

For position 1: locations[1] = 0, max((1 – 0),

1) to mini (1+0), 3) gives range = 1 to 1

For position 2: locations[2] = 2, max((2-2),

1) to min( (2+2), 3) gives range = 1 to 3

For position 3: locations[3] = 1, max( (3-1),

1) to min( (3+1), 3) gives range = 2 to 3

For the entire length of this road to be covered, only the light at position 2 needs to be activated.

Returns :         

int : the minimum number of street lights that must be activated

Constraints :

1<_n<_ 10^5

 O<_locations[i] <_ mini (n,100) (where 1 <_1<_10^5)

Sample Input For Custom Testing :

3 ->locations[] size n = 3

1 ->locations[] [1, 1, 1]

1 ->Sample Output

Sample Output :

1

Program :

 

// Hackerrank Java Coding Questions and Answers

//  Minimum streets lights

 

import java.util.Arrays;

import java.util.Comparator;

import java.util.Scanner;

class Pair{

          Integer a;

          Integer b;

          Pair(){

                  

          }

          Pair(Integer a,Integer b){

                   this.a=a;

                   this.b=b;

          }

          public Integer getA() {

                   return a;

          }

          public void setA(Integer a) {

                   this.a = a;

          }

          public Integer getB() {

                   return b;

          }

          public void setB(Integer b) {

                   this.b = b;

          }

         

}

class SortingPair implements Comparator<Pair>{

 

          @Override

          public int compare(Pair o1, Pair o2) {

                   if(o1.getA()==o2.getA()) {

                             if(o1.getB()<o2.getB()) {

                                      return 1;

                             }else {

                                      return 0;

                             }

                   }

                   if(o1.getA()<o2.getA()) {

                             return 1;

                   }else {

                             return 0;

                   }

          }

}

public class Application {

          public static void main(String args[]) {

                   Scanner sc = new Scanner(System.in);

                   int n = sc.nextInt();

                   int location[]=new int[n];

                   for(int i=0;i<n;i++) {

                             location[i]=sc.nextInt();

                   }

                   System.out.println(solve(location,n));

          }

          private static int solve(int[] location, int n) {

                   Pair range[] = new Pair[n];

                   for(int i=0;i<n;i++) {

                             int id=i+1;

                             range[i] = new Pair();

                             range[i].setA(Math.max(1, id-location[i]));

                             range[i].setB(Math.min(n, id+location[i]));

                   }

                   Arrays.sort(range,new SortingPair());

                   int i=0,ans=0;

                   while(i<n) {

                             Pair p=range[i];

                             ans++;

                             while(i+1<n && range[i].getA()==range[i+1].getA()) {

                                      p.b=Math.max(p.getB(), range[i+1].getB());

                                      i++;

                             }

                             while(i<n && range[i].getB()<=p.getB()) {

                                      i++;

                             }

                   }

                   return ans;

          }

}

 

For execution and output so check the video :





Comments

Post a Comment

Popular posts from this blog

Hackerrank Java Coding Questions and Answers - Maximum Passengers

  Hackerrank Java Coding Questions and Answers Maximum Passengers Problem Statement -:  A taxi can take multiple passengers to the railway station at the same time.On the way back to the starting point,the taxi driver may pick up additional passengers for his next trip to the airport.A map of passenger location has been created,represented as a square matrix. The Matrix is filled with cells,and each cell will have an initial value as follows: A value greater than or equal to zero represents a path. A value equal to 1 represents a passenger. A value equal to -1 represents an obstruction. The rules of motion of taxi are as follows: The Taxi driver starts at (0,0) and the railway station is at (n-1,n-1).Movement towards the railway station is right or down,through valid path cells. After reaching (n-1,n-1) the taxi driver travels back to (0,0) by travelling left or up through valid path cells. When passing through a path cell containing a passenger,the passe...
Post a Comment
Read more

HackerRank Java Coding Questions and Answers - Disk Space Analysis

  HackerRank   Java   Coding   Questions   and   Answers Disk Space Analysis Problem Statement -:   You are given an array, You have to choose a contiguous subarray of length ‘k’, and find the minimum of that segment, return the maximum of those minimums. Sample input 1 →  Length of segment x =1 5 →  size of space n = 5 1 → space = [ 1,2,3,1,2] 2  3  1  2  Sample output 3 Explanation The subarrays of size x = 1 are [1],[2],[3],[1], and [2],Because each subarray only contains 1 element, each value is minimal with respect to the subarray it is in. The maximum of these values is 3. Therefore, the answer is 3   Program :   // Hackerrank Java Coding Questions and Answers //   Disk Space Analysis   import java.util.*; class DiskSpace {   public static void main(String[] args) {   Scanner sc=new Scanner(System.in);   System.out.println...
Post a Comment
Read more

TCS CodeVita Coding Questions with Answers - Counting Rock Sample

  TCS CodeVita Coding Questions with Answers Counting Rock Sample Problem Description Question – :  Juan Marquinho is a geologist and he needs to count rock samples in order to send it to a chemical laboratory. He has a problem: The laboratory only accepts rock samples by a range of its size in ppm (parts per million). Juan Marquinho receives the rock samples one by one and he classifies the rock samples according to the range of the laboratory. This process is very hard because the number of rock samples may be in millions. Juan Marquinho needs your help, your task is to develop a program to get the number of rocks in each of the ranges accepted by the laboratory. Input Format :  An positive integer S (the number of rock samples) separated by a blank space, and a positive integer R (the number of ranges of the laboratory); A list of the sizes of S samples (in ppm), as positive integers separated by space R lines where the ith line containing two positive...
Post a Comment
Read more