0

I was trying to solve this dynamic programming question https://www.hackerrank.com/challenges/equal and my approach toward this is that

(1) Sort the array

(2) Find the max

(3) For each elements from 0 to array length -1 , try to make each element as close to max element by increasing it by 5 and then by 2 and lastly by 1.

(4) Sum number of 1,2,5 added to each number till now so that increments for this number can be clubbed together with previous one.

(5) Repeat step from 3 to 4 for max, max+1,max+2, max+5

Here is the algorithm, but it's failing some test cases . Please let me know where I am wrong here ?

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

public class Solution {

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

        Scanner scno = new Scanner(System.in);
        a = scno.nextInt();





        for ( int i = 0 ; i < a ; i++ )
        {
            no = scno.nextInt();
            no1 = new int[no];
            for ( int j = 0 ; j < no ; j++ )
            {
                no1[j] = scno.nextInt();
            }
            System.out.println(Solution.no(no1));
        }
    }

    private static int no(int[] nums)
    {
        int a = 0 , no = 0;
        int[] no1 = new int[]{0,0,0};

        if ( null == nums || 0 == nums.length || 1 == nums.length ) return 0;
        int arr[] = new int[]{1,2,5};

        Arrays.sort(nums);
        int max = nums[nums.length - 1];
        for ( int a1 = 0 ; a1 <= arr.length ; a1++ )
        {
            int temp = no;
            no = 0;
            Arrays.fill(no1, 0);
            if ( arr.length == a1 )
                max = nums[nums.length - 1];
            else
            {
                max = nums[nums.length - 1] + arr[a1];
                no1[a1]++;
                no++;
            }
            for ( int i = 0 ; i < nums.length - 1 ; i++ )
            {
                if ( i != 0 && nums[i] == nums[i-1] )
                    continue;
                else
                {
                    a = ( max - nums[i] );
                    for ( int j = 0 , n = a ; j < arr.length ; j++ )
                    {
                        a = n / arr[arr.length - 1 - j] ;
                        if ( a > no1[no1.length - 1 -j] )
                        {
                            no += a - no1[no1.length - 1 -j];
                            no1[no1.length - 1 -j] += a - no1[no1.length - 1 -j];
                        }
                        n = n % arr[arr.length - 1 - j];
                    }               
                }
            }
            if ( 0 != a1 ) no = Math.min(temp, no);
        }
        return no;
    }

}

Thanks In Advance

3
  • The code is working I want to know where did my algorithm go wrong. I have explained my algorithm in post too. Commented Aug 10, 2015 at 15:22
  • 1
    Firstly I would recommend using more readable variable names. Secondly you may help us by showing which test cases you failed. Lastly, I used a different approach: 1. sort the given array 2. reduce the minimum from all elements 3. initialize a counter 4. for each element in the array 4.1. while the element is not 0 4.1.1. if the element is greater than 5: reduce 5 from it and counter++ 4.1.2. else if the element is greater than 2: ... 4.1.3. else reduce 1 and counter++ 5. counter is now the solution Try to see if this algorithm relates to what you tried to do. what of it didn't you do? Commented Aug 10, 2015 at 16:54
  • 1
    thinking about it, i didn't even need to sort (as i suppose it would work if i simply found the minimum in an unsorted array and did the rest the same way) but i suppose 1 nlogn action vs 1 n action is hardly going to kill performance Commented Aug 10, 2015 at 16:56

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.