Water the plants complete solution with full logic in O(n), 28 days solution .(java)
Shivam Seth
Posted on February 22, 2021
Water the plants complete solution with full logic in O(n), 28 days solution of GFG.(java)
input = [2,3,4,-1,2,0,0,-1,0]
output [-1]
input = [-1,-1,2,2,0,0]
//code
import java.util.*;
class ONE {
int min_sp(int gal[], int n)
{
int arr[] = new int [n];
Arrays.fill(arr, -1);
for (int i=0;i<n;++i)
{
// System.out.println("its n "+n);
if (gal[i]==0)
{
// System.out.println("its arr[i] "+arr[i]);
arr[i]=Math.max(arr[i],i);
continue;
}
if (gal[i]!=-1)
{
int k=i+gal[i];
// System.out.println("its k "+k);
// int j=max (0,i-gal[i]);
int j=Math.max(0,i-gal[i]);
// System.out.println("its j "+j);
for(int sp = j;sp<=Math.min(n,k);++sp)
{if(sp==n)
continue;
arr[sp]=Math.max(k,arr[sp]);}
}
}
int c =0,i=0;
while(i<n)
{
// System.out.println("its i and n "+i+" "+n);
// System.out.println("its i and n "+i+" "+arr[i]);
if (i==-1||arr[i]==-1)
return -1;
++c;
i=arr[i]+1;
}
return c;
}
public static void main(String[] arr)
{
// Scanner in = new Scanner(System.in);
int gal[] ={2,3,4,-1,2,0,0,-1,0};
ONE s = new ONE();
int n=gal.length;
System.out.print(s.min_sp(gal,n));
}
}
Posted on February 22, 2021
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.