Recently while i was trying to solve a question where I am given a number of digits between 0 to 9 and have to find the largest integer divisible by 3.
I have read my code again but I am unable to find the test case where it fails. I will be grateful if the good people of stack overflow will help me find that test case. The testcase is a hidden testcase so I can't just print the elemets of the testcase.
import java.util.Arrays;
import java.util.LinkedList;
public class Main {
public int answer(int[] l) {
int b[] = new int[l.length];
int divb = 0;
int div = 0;
int t = 0;
int mi = 1;
int counter = 0;
LinkedList<Integer> ab = new LinkedList<Integer>();
Arrays.sort(l);
for (int i = 0; i < l.length; i++) {
ab.add(l[i]); //adding the elements to linkedlist after sorting them
div += l[i]; //adding all the elements in the array
b[i] = l[i] % 3;//we use b[i] to find whether we have 0,1,2 as one of the remainders
divb += b[i];
if (b[i] == 2) {
mi = 0;
}
if (b[i] == 1) {
counter = 1;
}
}
if (div % 3 == 1) {
if (counter == 1) {/*if counter is 1 that means we have atleast one element which has remainder 1 where we can remove that element to get a an integer in descending order of its digits which are divisible by 3*/
for (int i = 0; i < l.length; i++) {
if (b[i] == 1) {
div -= l[i];
ab.remove(i);
break;
}
}
} else {//if there is no such digit with remainder 1 but we have a number like 3,6,9 which is divible by 3 then we should return such a number.
int tk = 0;
for (int i = 0; i < l.length; i++) {
if (b[i] != 0) {
div-=l[i];
ab.remove(tk);
tk--;
}
tk++;
}
}
if (div % 3 != 0) {
return 0;
}
}
int k[] = new int[2];
if (div % 3 == 2) {//if the remainder is 2 then we have to remove oen digit with remainder as 2 or two digits with remainder as one. I tried to use various counters so that they don't effect each other
for (int i = 0; i < l.length; i++) {
if (b[i] == 2 && mi == 0) {
div -= l[i];
ab.remove(i);
break;
}
if (b[i] == 1 && t != 2 && mi == 1) {
div -= l[i];
k[t] = i;
t++;
}
if (t == 2) {
ab.remove(k[0]);
ab.remove(k[1] - 1);
break;
}
}
if (div % 3 != 0) {
return 0;
}
}
if (ab.size() >= 1) {//Here we will check whether size of result is more than zero just in case there was only element in the array which might have no more elements now.
int result = 0;
Integer[] res = ab.toArray(new Integer[ab.size()]);
for (int i = res.length - 1; i >= 0; i--) {
result = 10 * result + res[i];
}
return result;
}
else {
return 0;
}
}
public static void main(String[] arg)
{
int a[]={7,7,7,6};
Main d=new Main();
int f=d.answer(a);
System.out.print(f);
}
When trying to write a tricky algorithm like this it's often a good idea to write a second, simpler implementation to test it against.
In this case the obvious candidate is a brute force approach, where you generate all possible permutations of all possible subsets of your input digits, test if the resulting number is divisible by 3 and keep track of the max such number encountered.
Here's some code that implements this idea:
public class BruteDiv3
{
public static int maxDiv3(int[] arr)
{
return generateSubsets(arr, new BitSet(), 0, 0);
}
static int generateSubsets(int[] digits, BitSet selected, int pos, int maxDiv3)
{
if (pos == digits.length)
{
List<Integer> subset = toSubset(digits, selected);
if (!subset.isEmpty())
{
maxDiv3 = permuteSubset(subset, 0, maxDiv3);
}
return maxDiv3;
}
boolean duplicate = false;
for (int i = pos - 1; i >= 0; i--)
{
if (digits[i] == digits[pos] && !selected.get(i))
{
duplicate = true;
break;
}
}
if (!duplicate)
{
selected.set(pos);
maxDiv3 = generateSubsets(digits, selected, pos + 1, maxDiv3);
selected.clear(pos);
}
maxDiv3 = generateSubsets(digits, selected, pos + 1, maxDiv3);
return maxDiv3;
}
static int permuteSubset(List<Integer> subset, int pos, int maxDiv3)
{
if (pos == subset.size())
{
int num = toInteger(subset);
if (num % 3 == 0 && num > maxDiv3)
{
maxDiv3 = num;
}
return maxDiv3;
}
maxDiv3 = permuteSubset(subset, pos + 1, maxDiv3);
for (int i = pos + 1; i < subset.size(); i++)
{
if (!subset.get(pos).equals(subset.get(i)))
{
List<Integer> permSubset = new ArrayList<>(subset);
Collections.swap(permSubset, pos, i);
maxDiv3 = permuteSubset(permSubset, pos + 1, maxDiv3);
}
}
return maxDiv3;
}
static List<Integer> toSubset(int[] arr, BitSet on)
{
List<Integer> ss = new ArrayList<>();
for (int i = 0; i < arr.length; i++)
{
if (on.get(i))
ss.add(arr[i]);
}
return ss;
}
static int toInteger(List<Integer> digits)
{
int num = 0;
for (int pow10 = 1, i = digits.size() - 1; i >= 0; i--, pow10 *= 10)
{
num += digits.get(i) * pow10;
}
return num;
}
}
With this in hand we can now write a routine to compare the numbers from the brute force approach with the numbers from your routine with random input.
static void compare(int n)
{
int[] arr = new int[n];
Random r = new Random();
while (true)
{
for (int i = 0; i < n; i++)
arr[i] = r.nextInt(10);
int maxBrute = BruteDiv3.maxDiv3(arr);
int maxSO = new Main().answer(arr);
if (maxBrute % 3 != 0)
System.out.println("Bad Brute: " + maxBrute);
if (maxSO % 3 != 0)
System.out.println("Bad SO: " + maxSO);
if (maxBrute != maxSO)
{
System.out.println(Arrays.toString(arr) + " " + maxBrute + " " + maxSO);
}
}
}
For input up to n=4 things seem to be OK.
However, by n=5 we get:
[2, 5, 5, 5, 8] 855 0
[2, 5, 8, 8, 8] 888 0
[2, 2, 5, 5, 5] 555 0
...
Where your routine seems to be returning 0.
For n=8 we have
[0, 2, 3, 3, 5, 5, 8, 8] 885330 330
[2, 2, 3, 5, 5, 5, 9, 9] 995553 993
[2, 2, 2, 3, 5, 5, 6, 9] 965532 963
...
Hopefully you can use the above routines to help track down the issues in your code.