CODEWITHSUNDEEP
javaalgorithm
anonymous
anonymous

Reputation: 1968

Algorithm failing only for one test cases at hackerrank

I tried to attempt hackerrank problem of https://www.hackerrank.com/challenges/poisonous-plants and come up with below algorithm. I require some help as my solution is failing only 2 test cases and they are large data set so difficult to debug. I am including link to test case http://ideone.com/B2WWaH its giving 204 answer but correct answer as per brute force method is 16. In simple words problem is that given a non empty array of positive integers in each iteration array element which is greater than it's previous is removed. After how many iteration there will be no removal.

Problem

There are N plants in a garden. Each of these plants has been added with some amount of pesticide. After each day, if any plant has more pesticide than the plant at its left, being weaker than the left one, it dies. You are given the initial values of the pesticide in each plant. Print the number of days after which no plant dies, i.e. the time after which there are no plants with more pesticide content than the plant to their left.

Input Format

The input consists of an integer N. The next line consists of N integers describing the array P where P[i] denotes the amount of pesticide in plant i.

Constraints

Output Format

Output a single value equal to the number of days after which no plants die.

I have made some observation

(1) First plant will always survive as there is no plant on its left side.

(2) In last longest decreasing sub-sequence starting from first plant will survive.

(3) We just have to find out how many days it will take for plant between elements of these sub-sequence to die.

(4) Came up with algorithm to track plant on which day it dies.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class No {

    public static void main(String[] args) throws FileNotFoundException {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        int a = 0 , no = 0 ;

        Scanner scno = new Scanner(new File("D:\\no.txt"));
        a = scno.nextInt();
        int[] arr = new int[a];





        int n[] = new int[a]; int n1 = 0;
        for ( int i = 0 ; i < arr.length ; i++ )
        {
            arr[i] = scno.nextInt();
            if ( 0 != i )
            {
                if ( arr[i] > arr[i-1] )
                {
                    n[1] = arr[i];
                    no = Math.max(no, 1);
                }
                else if ( arr[i] > arr[a] )
                {
                    for ( int j = no ; j >= 0 ; j-- )
                    {
                        if ( 0 == j )
                        {
                            n[++no] = arr[i];
                            break;
                        }
                        if ( arr[i] > n[j] )
                        {
                            n[j] = arr[i];
                            break;
                        }                       
                    }
                }
                else
                {
                    a = i;
                    n1 = Math.max(n1, no);
                    no = 0;
                    Arrays.fill(n, 0);
                }
            }
            else
            {
                a = i;
            }

        }
        System.out.println(Math.max(n1, no));   
    }
}

Upvotes: 3

Views: 3661

Answers (1)

innoSPG
innoSPG

Reputation: 4656

First of all, you have to follow some steps to solve any problem. In this type of problem, you have to:

  1. Read all the data first, this means an independent loop to read all the plant data.
  2. You apply your evolution model if there is one. This is another independent loop. The assumptions you have made are not sufficient. I do not know if it will be possible to get it in one shot, you will easily define those characteristics if you first write a solution that works. The solution that will work for sure is to iterate and kill plants. Iterate from the right and kill the plant that satisfies the dying condition. And repeat until one loop doesn't kill any plant. The number of those days is the nomber of loops you have made minus one (the last that did not kill any plant). ArrayList will make your life simple.

in short, your can declare your data array as

    ArraList<int> arr = new ArraList(a)

fill it as (after reading the size a of the vector

    for ( int i = 0 ; i < a ; i++ ) arr.add(scno.nextInt());

and use a subroutine like this to do the job (this is just an indication, I did not test it)

    private static int numberDaysNoD(ArraList<int> arr){
        int nDays = 0;
        boolean haveKilled = true;
        while(haveKilled){
            haveKilled = false;
            for(int i = arr.size()-1; i>0; i--){
                if(arr.get(i)>arr.get(i-1)){
                    arr.remove(i);
                    haveKilled = true;
                }
            }
            nDays++;
        }
        return nDays--
    }

Second there is one thing missing in the statement of your problem. Does the pesticide level in plants evolves? What is the evolution model? Or simply there is no evolution and each day, we simply kill those that have more that their left neighbor (this automatically change the left neighbor if one dies) and wait for the next day to repeat?

Upvotes: 1

Related Questions