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