Minimum Lights to Activate Java Snippet Class

Minimum Lights to Activate Problem in Java

In prison, there is a hallway that is N units long. Given an N-dimensional array A. If the light at the ith position is broken, the ith index of this array is 0, otherwise it is 1.

All lights have a specified power B, and if they are all in position X, they will all be able to illuminate the hallway from [X-B+1, X+B-1].

At first, all of the lights are off.

If the entire corridor cannot be lit, return -1 instead of the minimal number of lights that must be turned on.

Let’s understand the code demonstration of above problem in Java.

Code:

// import the packages  
import java.util.*;  
import java.io.*;
public class MinimumLights 
{  
    // first find the mininmum one among the two x and y 
    int min(int x, int y)  
    {  
        if(x > y)  
        {  
            return y;  
        }  
        return x;  
    }  
    // next find the maximum one among the two x and y 
    int max(int x, int y)  
    {  
        if(x > y)  
        {  
            return x;  
        }  
        return y;  
        
    }  
    // a technique that determines the bare minimum of lights needed to illuminate the entire hallway.  
    public int minnumberlight(int larr[], int lPower)  
    {  
        int n = larr.length;  
        int dparr[] = new int[n + 1];  
        for(int i= 0; i < n + 1; i++)  
        {  
            dparr[i] = Integer.MAX_VALUE / 2;  
        }  
        // Assume that dp[j] represents the minimum number of lights necessary to illuminate the corridor up to the jth location.  
      
        dparr[0] = 0; //0 bulbs are needed to cover the 0th region.
      
        for(int i = 0; i < n; i++)  
        {  
            if(larr[i] == 0)   
            {  
            // The lamp is broken. Check for the next light as a result. 
            continue;  
            }  
            int left = max(0, i - lPower + 1) + 1; // +1 as dpArr.length == size + 1  
        int right = min(i + lPower - 1, n - 1) + 1;  
          
        // calculating the bare minimum of lights needed to illuminate the corridor until the jth position
        for(int j = left; j <= right; j++)  
        {  
            dparr[j] = min(dparr[j], dparr[left - 1] + 1);  
        }  
    }  
   if(dparr[n] == Integer.MAX_VALUE / 2)  
    { 
        return -1; 
        
    }  
    return dparr[n];  
        
    }  
// main method  
public static void main(String[] argvs)  
{  
// creating an object of the class MinimumLights
    MinimumLights obj = new MinimumLights();  
    int larr[] = {1, 1, 0, 1, 1};  
    int n = larr.length;  
    int lPower = 3;  
    int ans = obj.minnumberlight(larr, lPower);  
    System.out.println("for the given lights: ");   
    for(int i = 0; i < n; i++)  
    {  
        System.out.print(larr[i] + " ");  
    }  
    System.out.println();  
    if(ans != -1)  
    {  
        System.out.println("The bare minimum of lights required to illuminate the entire corridor is: " + ans);  
    }  
    else  
    {  
        System.out.println("It is impossible to illuminate the entire corridor.");     
    }  
    int larr1[] = {0, 0, 0, 1, 1, 1, 1, 1, 1};  
    n = larr1.length;  
    lPower = 3;  
    System.out.println();  
    ans = obj.minnumberlight(larr1, lPower);  
    System.out.println("For the following lights: ");   
    for(int i = 0; i < n; i++)  
    {  
        System.out.print(larr1[i] + " ");  
    }  
    System.out.println();  
    if(ans != -1)  
    {  
        System.out.println("The minimum number of lights to light up the whole corridor is: " + ans);  
    }  
    else  
    {  
        System.out.println("It is not possible to light up the whole corridor.");     
    }  
  
}  
}  

Output:

cd /home/cg/root/6367601bbbf54
for the given lights: 
1 1 0 1 1 
The bare minimum of lights required to illuminate the entire corridor is: 2
For the following lights: 
0 0 0 1 1 1 1 1 1 
It is not possible to light up the whole corridor.

Try to turn the problem into a different form or approach like you normally do while solving difficulties. Usually, this will make the issue simpler. When we read this problem, one thought that comes to mind is to divide it into pairs of ranges that the light illuminates.

Nested for-loops were utilised to calculate the solution. Consequently, the program's time complexity is O(n2). Additionally, we added an auxiliary array to store the results, making the program's space complexity O(n), where n is the total number of entries in the array.