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!

I don't really know what you are trying to do in your code, but if I understood your problem correctly, all you need to do is to first, find all combinations of the four digits that sums up to a number that is divisible by 3. Then, find the largest one. — Azim
– Azim, Commented Sep 29, 2018 at 23:18

kkica · Accepted Answer · 2018-10-01 08:49:24Z

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:

Sort the digits.
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.

edited Oct 1, 2018 at 8:49

answered Sep 29, 2018 at 23:13

kkica

4,1041 gold badge22 silver badges41 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

John Smith Over a year ago

There is a problem with that, let's say that the array is 9 digits long, it would take a really long time to try out every combination. I need a fast way to do it.

kkica Over a year ago

You will not try every combination. You will try at worst case every "Group" of combinations. For example: You have a group of 8 digits, where the sum is divisible by 3. There are 8! combinations in that group, but you will not try any of those 40320. You have the digits sorted and you can find the number directly from there. What the program will do in my solution is check only the combinations. 2*(C9,9+c9,8+C9,7+C9,6+C9,5)=2(1+9+36+84+126)=512 combinatios MAX. But you can stop once you find one group that is divisible by 3, as long as you choose the order well

John Smith Over a year ago

I don't understand, can u please send a code snippet?

kkica Over a year ago

@MBo You mean, check if there is a number a%3=k first.

MBo Over a year ago

@Kristjan Kica Yes, it is more correct. Will delete comment and make new

|

Egor · Accepted Answer · 2018-09-30 01:27:42Z

0

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

answered Sep 30, 2018 at 1:27

Egor

1,40912 silver badges26 bronze badges

2 Comments

John Smith Over a year ago

No, it won't, because you don't need to use all the ints in the int array.

John Smith Over a year ago

Inputs: (int list) l = [3, 1, 4, 1, 5, 9] Output: (int) 94311 I dont use the 5 from the input array

Collectives™ on Stack Overflow

Java: Possible Combinitions of an Array

2 Answers 2

6 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related