Java: Possible Combinitions of an Array

Question

I am working on a java problem:

Problem:

The user enters an array of ints, the array can be of size 1-9. I need to rearrange the array so that it prints the greatest value, which is divisible by 3. I do not need to use all the ints in the array.

Examples:

Inputs: (int list) l = [3, 1, 4, 1]

Output: (int) 4311

Inputs: (int list) l = [3, 1, 4, 1, 5, 9]

Output: (int) 94311

--

I spent around 5 hours on this so far. My code works, but it pretty much tries every combination until one works. I need a more efficient code.

This is my code:

public class CodedMessage {
	public static int zero = 0;
	public static int one = 0;
	public static int two = 0;
	public static int three = 0;
	public static int four = 0;
	public static int five = 0;
	public static int six = 0;
	public static int seven = 0;
	public static int eight = 0;
	public static int nine = 0;

	public static int best = 0;
	public static int current = 0;

	public static int newZero = 0;
	public static int newOne = 0;
	public static int newTwo = 0;
	public static int newThree = 0;
	public static int newFour = 0;
	public static int newFive = 0;
	public static int newSix = 0;
	public static int newSeven = 0;
	public static int newEight = 0;
	public static int newNine = 0;

	public static void main(String[] args) {
		int[] myIntArray = {3,1,4,1};

		System.out.println(answer(myIntArray));
	}

	public static int answer(int[] l) {
		String line ="";
		for (int c : l) {
			line += c;
		}
		zero = line.length() - line.replace("0", "").length();
		one = line.length() - line.replace("1", "").length();
		;
		two = line.length() - line.replace("2", "").length();
		;
		three = line.length() - line.replace("3", "").length();
		;
		four = line.length() - line.replace("4", "").length();
		;
		five = line.length() - line.replace("5", "").length();
		;
		six = line.length() - line.replace("6", "").length();
		;
		seven = line.length() - line.replace("7", "").length();
		;
		eight = line.length() - line.replace("8", "").length();
		;
		nine = line.length() - line.replace("9", "").length();
		;
		if (Integer.parseInt(line)%3 != 0) {
			
		}else {
			possibleStrings(l.length, l, "");
		}
		
		

		return best;

	}

	public static String possibleStrings(int maxLength, int[] alphabet, String curr) {


		if (!curr.equals("")) {
			current = Integer.parseInt(curr);
			
		}

		if (current > best) {
			if (current % 3 == 0) {
				String line = Integer.toString(current);
				newZero = line.length() - line.replace("0", "").length();
				newOne = line.length() - line.replace("1", "").length();
				;
				newTwo = line.length() - line.replace("2", "").length();
				;
				newThree = line.length() - line.replace("3", "").length();
				;
				newFour = line.length() - line.replace("4", "").length();
				;
				newFive = line.length() - line.replace("5", "").length();
				;
				newSix = line.length() - line.replace("6", "").length();
				;
				newSeven = line.length() - line.replace("7", "").length();
				;
				newEight = line.length() - line.replace("8", "").length();
				;
				newNine = line.length() - line.replace("9", "").length();
				;

				if (zero >= newZero && one >= newOne && two >= newTwo && three >= newThree && four >= newFour
						&& five >= newFive && six >= newSix && seven >= newSeven && eight >= newEight
						&& nine >= newNine) {
					best = current;
				}
			}

		}
		
		if (curr.length() == maxLength) {
			if (!curr.equals("") &&Integer.parseInt(curr)%3 != 0) {
				return "hi";
			}
		} else {
			for (int i = 0; i < alphabet.length; i++) {
				String oldCurr = curr;
				curr += alphabet[i];

				possibleStrings(maxLength, alphabet, curr);
				curr = oldCurr;
			}
		}
		return "hi";
	}

}

Can someone please make it more efficient, I tried but wasen't able to.

Thanks!

Answer 1

For a number to be divisible by 3, it needs the sum of the digits to be divisible by 3. You can procced like this:

1. Sort the digits.

2. Use the sorted digits to find the group with the biggest number of digits. Do this by first checking if the total sum is divisible by 3. Then try with n-1 biggest digits, and so on. The first group you find is what you are looking for

Edit: based on a suggestion in comments For the second step. Find k=sum%3;

if(k==0) you have the solution.

If not, then check all the digits starting from the lowest (the end of the array) if digit%3=k. If so, remove it and you find the solution. If no digit does that, try with 2 digits, 3 digits, and so on.

Answer 2

You just need to sort the array in descending order of numbers and write them in one line. Will this solve the problem?