CareerCup

I think there is no need to consider pairs of numbers.
Three cases:
1) Sum of digits divisible by 3 - no need to do anything.
2) Sum of digits equals 1 or 2 modulo 3. Search for smallest digit that gives same remainder modulo 3
3) Sum of digits equals 1 or 2 modulo 3 = x. but all digits are 3-x. Just take 2 smallest digits and remove them.

ah, sorry, in your code you are doing exactly that thing. (explanation confused a litl bit)

@bob: Thanks!
I have just made some changes into my explanation.

My explanation for the case divisible by 3 is little bit confusing (compared to actual implementation).
However, if the question asked for other division, e.g. divisible by 9, then that explanation could still be applied. Isn't it?

I dont think your code is right though !!

@Tony Stark: have you tried it? Or, you may refer to bob's comments above for explanation.

I think it may be wrong for this input A = 42110.

I think it is giving correct answer 420 ...... Why u think it is wrong? give me test cases.....

The answer should be 4110.

/**
 * 
 */
package Amazon;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;

/**
 * @author mangesh
 * 
 */
public class GenerateMAX {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Integer a[] = { 4,2,1,1,0 };
		LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(a));
		ArrayList<Long> max = new ArrayList<Long>();
		Collections.sort(list);
		if (list.get(0) != 0) {
			System.out.println("Can not find such number!!!");
			return;
		}
		int k = 1;
		int nocosiderDigit = -1;
		boolean remove = false;
		while (true) {

			long number = list.get(0);
			int pow = 1;
			for (int i = 1; i < list.size(); i++) {
				if (nocosiderDigit == i)
					continue;
				number += (long) (list.get(i) * Math.pow(10, pow++));
			}
			if (number % 3 == 0) {
				max.add(number);

			}
			while (true) {
				if (list.get(k) % 3 != 0) {
					if (!remove)
						nocosiderDigit = list.indexOf(list.get(k));
					else
						list.remove(k);
					k++;
					break;
				}
				k++;

				if (k >= list.size())
					break;

			}
			if (k >= list.size()) {
				if (max.size() == 0 && !remove) {
					k = 1;
					remove = true;
				} else {
					break;
				}

			}

		}
		if (max.size() > 0) {
			Collections.sort(max);
			System.out.println(max.get(max.size() - 1));
			System.out.println(max.toString());
		} else
			System.out.println("Can not find such number!!!");

	}
}

we can do something for 3 if it's originally impossible, by ignoring one or two digits.
The example suggested so.

Actually answer should be 8760 .....

I used the BFS method by deleting one digit in each level to get the result.
And also use a Map to filter the duplicate node.
For example:
level 0: 8761
level 1: 876 871 861 761
level 2: 87 86 76 .....

import java.util.*;
public class MaxNumber {

    public static void main(String[] args) {
        int[] arr = {7,7,7,6,0};
        MaxNumber obj = new MaxNumber();
        int result = obj.getMaxNumber(arr);
        System.out.println(result);
    }

    public int getMaxNumber(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        Arrays.sort(arr);
        int num = 0;
        for (int i = arr.length - 1; i >= 0; i--) {
            num = num * 10 + arr[i];
        }
        //System.out.println(num);
        if (num % 10 != 0) {
            return -1;
        }
        // delete last digit '0'
        num = num / 10;
        Queue<Integer> queue = new LinkedList<>();
        // filter duplicate case;
        Map<Integer, Boolean> map = new HashMap<>(); 
        queue.offer(num);
        while (queue.size() != 0) {
            int top = queue.poll();
            if (isValidForDividByThree(top)) {
                return top * 10;
            }
            List<Integer> allSubNum = getSubNodesByDeleteOneDigit(top);
            for (Integer i : allSubNum) {
                if (!map.containsKey(i)) {
                    queue.offer(i);
                    map.put(i, true);
                }
            }
        }
        return -1;
    }

    private List<Integer> getSubNodesByDeleteOneDigit(int num) {
        List<Integer> resultList = new ArrayList<>();
        int length = getLength(num);
        for (int i = 0; i < length; i++) {
            int result = deleteIndexAtI(num, i);
            resultList.add(result);
        }
        return resultList;
    }

    private int deleteIndexAtI(int num, int index) {
        int lastPartNumber = num % (int)Math.pow(10.0, index);
        int firstPartNumber = num / (int)Math.pow(10.0, index + 1);
        firstPartNumber = firstPartNumber * (int)Math.pow(10.0, index);
        return firstPartNumber + lastPartNumber;
    }

    private int getLength(int num) {
        int length = 0;
        while (num != 0) {
            length++;
            num = num / 10;
        }
        return length;
    }

    private boolean isValidForDividByThree(int num) {
        int sum = 0;
        while (num != 0) {
            sum += num % 10;
            num = num / 10;
        }
        if (sum % 3 == 0) {
            return true;
        }
        return false;
    }

}