CareerCup

You can refer to the following logic:
a.If zero does not exist in the array then number is not possible.
b.Sort the whole array and then calculate the sum of the whole array.If the sum of the digits is divisible by 3 then the number can be formed and generate the number.
c.If sum of digits is not divisible by 3 then as the array is sorted take every number and subtract it from the sum just calculated above. If sum is divisible by 3 then generate the number and if not then continue further in this fashion.
d.The array is sorted to get the largest number formed from the array.
Here is the below code:

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a,const void *b)
{
    return (*(int *)a-*(int *)b);
}
int calculateSum(int arr[],int n)
{
    int i,sum=0;
    for(i=0;i<n;i++)
        sum=sum+arr[i];
    return sum;
}
int generateNumber(int arr[],int j,int n)
{
    int i;
    int num=0,power,k=0;
    for(i=j;i<n;i++)
    {
        power=(arr[i]*pow(10.0,k));
        num=power+num;
        k=k+1;
    }
    //to include last zero in the number
    return (num+1)*10;
}
void findSum(int arr[],int n)
{
    int i=0,sum,num;
    if(arr[i]!=0)
    {
        printf("\nNumber not possible");
        return;
    }
    else
    {
        sum=calculateSum(arr,n);
        if(sum%3==0)
        {
            num=generateNumber(arr,1,n);
            printf("The number is %d ",num);
            return;
        }
        else
        {
            for(i=0;i<n;i++)
            {
                int c=sum;
                sum=sum-arr[i];
                if(sum%3==0)
                {
                    num=generateNumber(arr,i+1,n);
                    printf("The number is %d ",num);
                    return;
                }
               else
              {
                  sum=c;
              }
            }
        }
    }
}
void printArray(int arr[],int n)
{
	int i;
	for(i=0;i<n;i++)
		printf(" %d ",arr[i]);
}
int main()
{
    int arr[]={6,7,8,0,1,2};
    int i;
    int n=sizeof(arr)/sizeof(arr[0]);
    qsort(arr,n,sizeof(int),compare);
    printArray(arr,n);
    findSum(arr,n);
}

the test cases you given may not be correct, 8610 also can be divisible by 2,3,5.
several points:
- the latest digit must be 0;
- all digits add up sum can divide by 3;

The result should be 8760.

for the first case, the out put should be 8760

Several mathematical properties:
(1) Number is divisible by both 2 & 5 only when last digit is 0
(2) Number is divisible by 3 only when sum of digits is divisible by 3

Having said that, this is my algorithm:
(1) First sort all the digits
(2) If the ones-digit isn't 0, then no solution
(3) Otherwise, the sum of digits modulo 3 is either 0, 1 or 2
(4) If mod3 is 2 and there isn't at least a digit with modulo=2 or 2 digits with modulo=1, then no solution
(5) If mod3 is 1 and there isn't at least a digit with modulo=1 or 2 digits with modulo=2, then no solution
(6) Otherwise, we proceed to create the number by carefully checking which digits we should skip over to ensure the final number has modulo=0
(7) The code is actually rather messy and I don't know how to drastically clean it up

static int maxDivisible(int[] arr) {
	Arrays.sort(arr);

	int mod3 = 0;
	int numMod2 = 0;
	int numMod1 = 0;
	for(int i : arr) {
		int modulo = i%3;
		mod3 = (mod3 + modulo)%3;
		if(modulo == 2)
			numMod2++;
		else if(modulo == 1)
			numMod1++;
	}
	if(arr[0] != 0)
		return -1;
	if(mod3 == 2 && numMod2 < 1 && numMod1 < 2)
		return -1;
	if(mod3 == 1 && numMod1 < 1 && numMod2 < 2)
		return -1;

	int total = 0;
	int multiplier = 1;
	for(int i=0; i<arr.length; i++) {
		int digit = arr[i];
		int modulo = digit%3;
		if(mod3 == 2) {
			if(modulo == 2) {
				// skip this digit
				mod3 = 0;
				continue;
			} else if(modulo == 1 && numMod2 == 0) {
				// skip this digit only if numMod2 == 0,
				// because it's better to remove 1 digit than 2 digits
				mod3 = 1;
				continue;
			}
		} else if(mod3 == 1) {
			if(modulo == 1) {
				mod3 = 0;
				continue;
			} else if(modulo == 2 && numMod1 == 0) {
				mod3 = 2;
				continue;
			}
		}
		total += digit * multiplier;
		multiplier *= 10;
	}
	return total;
}

As people have mentioned, a zero must be the final digit. The sum of the rest of the numbers must be divisible by 3.
First off, we can select any numbers which are multiples of 3, since when added to the other numbers they will not change its 3-divisibility.
Next, for the remaining numbers each number is either one or two removed from a 3-divisible (e.g. 4 is one removed, 5 is two removed, six is divisible again).

That means that for the rest of the numbers, you have to remove at most two numbers (two one-removed numbers) since if you have 3 numbers of any combination (2x1 + 1x2 = 3 + 1, so remove a one; 1x1 2x2 = 3 + 2, so remove a two; 3x1 or 3x2 is fine, since they'll be 3-divisible) then you will find a way to use at least two of those numbers.
Look through the list, remove the smallest possible numbers, and sort the remaining numbers from largest to smallest to make your result.

sites.google.com/site/spaceofjameschen/home/lambda/generate-the-maximum-number-using-the-digits-in-the-array-such-that-it-is-divisible-by-2-3-and-5

int residual = sum % 3;
if(residual != 0){
int modulo1 = count_if(arr, arr + len, [](int i)->bool{ return i % 3 == 1; });
int modulo2 = count_if(arr, arr + len, [](int i)->bool{ return i % 3 == 2; });
int replaceMod;
int cnt;

if(modulo2 == 0){
replaceMod = 1;
cnt = residual;
}
else if(modulo1 == 0){
replaceMod = 2;
cnt = (residual == 1) ? 2 : 1;
}
else {
replaceMod = residual;
cnt = 1;
}

newLen -= cnt;

for(int i = len - 2; i >= 0; --i){
if(arr[i] % 3 == replaceMod){
arr[i] = 0;
cnt --;

if(cnt == 0) break;
}
}
}

first check for 0 .if no of 0 are zero return -1;
else
count no of 9,8,7,6,5,4,3,2,1,0 in arry ..
as 9,6,3 are always divisble by 3.so they will be in answer always..
now check for

8,8,8
8,8,2
8,5,2
8,2,2
7,7,7
7,7,1
7,4,1
5,5,5
5,2,2
4,4,4
4,4,1
2,2,2
1,1,1
8,7
8,4
8,1
7,5
7,2
5,4
5,1
4,2
2,1
combination

public final class MaxNumberGenerator {
	
	
	private MaxNumberGenerator(){
		super();
	}

	private static final BigInteger ONE_MINUS = new BigInteger("-1");

	public static BigInteger findMax( int[] baseArr ){
		
		int zeroElemIndex = findZeroIndex(baseArr);
		
		// check for '0' element index
		if( zeroElemIndex < 0 ){
			return ONE_MINUS;
		}
		
		// copy array except zero index
		int[] arr = copyArrayExceptOneElement(baseArr, zeroElemIndex);
		
		sortInReverseOrder( arr );

		List<List<Integer>> rems = remBuckets( arr, 3);
		
		List<Integer> maxNumber = merge(listToArr(rems.get(0)), listToArr(rems.get(1)), listToArr(rems.get(2)));	
		maxNumber.add(0);
		
		return decimalListToInt(maxNumber);
	}
	
	
	@SuppressWarnings("serial")
	private static List<List<Integer>> remBuckets(int[] arr, int divValue){
		
		final List<Integer> zero = new ArrayList<>();
		final List<Integer> one = new ArrayList<>();
		final List<Integer> two = new ArrayList<>();
		
		for( int val : arr ){
			int rem = val % divValue;
			
			if( rem == 0 ){
				zero.add( val );
			}
			else if( rem == 1){
				one.add( val );
			}
			else {
				two.add( val );
			}
		}
		
		return new ArrayList<List<Integer>>(){{ add(zero); add(one); add(two); }};
	}
	
	private static int[] copyArrayExceptOneElement(int[] baseArr, int indexToSkip){
		
		int[] arr = new int[baseArr.length-1];
		int arrIndex = 0;
				
		for( int i =0; i < arr.length;  ){
					
			if( arrIndex != indexToSkip ){
				arr[i] = baseArr[arrIndex];
				++i;
			}
					
			++arrIndex;
		}
		return arr;		
	}
	
	private static void sortInReverseOrder( int[] arr ){ 
		Arrays.sort( arr );	
		
		int left = 0;
		int right = arr.length-1;
		
		while( left < right ){
			
			int temp = arr[left];
			arr[left] = arr[right];
			arr[right] = temp;
			
			++left;
			--right;
		}
	
	}
	
	private static int findZeroIndex( int[] arr ){
		
		for( int i = 0; i < arr.length; i++ ){
			if( arr[i] == 0 ){
				return i;
			}
		}
		
		return -1;
	}
	
	private static BigInteger decimalListToInt( List<Integer> list ){
		
		Iterator<Integer> it = list.iterator();
		
		BigInteger res = BigInteger.ZERO;
		
		while( it.hasNext() ){
			res = res.multiply( BigInteger.TEN).add( BigInteger.valueOf(it.next()) );
		}
		
		return res;
	}
	
	private static int[] listToArr( List<Integer> list ){
		int[] arr = new int[list.size()];
		
		for( int i =0; i < arr.length; i++ ){
			arr[i] = list.get(i);
		}
		return arr;
	}
	
	private static List<Integer> merge( int[] zero, int[] one, int[] two  ){
				
		List<Integer> number = new ArrayList<>();
		
		int zeroIndex = 0;
		int oneIndex = 0;
		int twoIndex = 0;			
		
		while( oneIndex < one.length ){
			
			int zeroValue = (zeroIndex < zero.length ? zero[zeroIndex] : Integer.MIN_VALUE);
			
			if( twoIndex >= two.length ){
				
				if( oneIndex >= one.length - 2 ){
					break;
				}
				
				while( oneIndex < one.length - 2 ){
					
					for( int i =0; i < 3; i++, oneIndex++ ){
						
						while( zeroIndex < zero.length && zero[zeroIndex] > one[oneIndex] ){
							number.add( zero[zeroIndex] );
							++zeroIndex;
						}
						
						number.add( one[oneIndex] );
					}
				}				
			}
			else {			
				if( one[oneIndex] > zeroValue ){
					
					if( two[twoIndex] > zeroValue ){
						number.add( Math.max(one[oneIndex] , two[twoIndex]) );
						number.add( Math.min(one[oneIndex] , two[twoIndex]) );
						
						++oneIndex;
						++twoIndex;
					}
					else {
						number.add( one[oneIndex] );
						if( zeroValue != Integer.MIN_VALUE){
							number.add( zeroValue );
							zeroValue = zero[zeroIndex++];
						}
						number.add( two[twoIndex] );						
						
						++oneIndex;
						++twoIndex;									
					}
				}
				else if( two[twoIndex] > zeroValue ){
					
					number.add( two[twoIndex] );					
					if( zeroValue != Integer.MIN_VALUE){
						number.add( zeroValue );
						zeroValue = zero[zeroIndex++];
					}	
					number.add( one[oneIndex] );					

					++oneIndex;
					++twoIndex;	
					
				}
			}
		}		
		
		while( zeroIndex < zero.length ){
			number.add( zero[zeroIndex] );	
			++zeroIndex;
		}		
		
		return number;
	}

	

}

test cases:

assertEquals( new BigInteger("8760"), MaxNumberGenerator.findMax( new int[]{1,8,7,6,0}) );		
		assertEquals( new BigInteger("87600"), MaxNumberGenerator.findMax( new int[]{1,8,0,7,6,0}) );		
		assertEquals( new BigInteger("97770"), MaxNumberGenerator.findMax( new int[]{7,7,7,9,0}) );
		assertEquals( new BigInteger("77760"), MaxNumberGenerator.findMax( new int[]{7,7,7,6,0}) );		
		assertEquals( new BigInteger("870"), MaxNumberGenerator.findMax( new int[]{7,0,8}) );
		
		assertEquals( new BigInteger("-1"), MaxNumberGenerator.findMax( new int[]{7,7,7,6}) );		
		
		int[] bigArr = new int[]{3, 9, 3, 7, 0, 7, 0, 4, 6, 9}; 		
		assertEquals( new BigInteger("9977643300"), MaxNumberGenerator.findMax(bigArr) );

Step1: Sort the digits {8,7,6,1,0}
Step2: if least number is not zero , return false
Step3: construct any array with reminders {2,1,0,1,0}
Step4: get the sum of reminders and get the reminder of this sum from 3. (2+1+0+1+0)%3 = 4 %3 = 1
step5: if reminder is zero, format the number from sorted array and print it. If reminder is not zero, move to next step
Step6: Check if the reminder exists in the list.
step7: if YES, remove the least number yielding that reminder. {2,1,0,1,0} -- remove 1 in this case
if NO, start removing the least numbers that yield non-zero reminders, so that the sum of reminders of removed numbers equal to calculated reminder.

Format the number with remaining digits.

Code:

#include <iostream>

using namespace std;


long getMaxNumber(int a[],int size);

int main()
{
    int a[] = {1,2,4,9,0,0};
    
    int n = sizeof(a)/sizeof(a[0]);
    
    long number = getMaxNumber(a,n);
    
    cout <<"number : "<<number <<endl;
    
    getchar();
    return 0;
    
}

//bubble sort, assending order
void sort(int a[],int n)
{
     for(int i = 0 ; i < n  ; i++)
     {
             for(int j = 0 ; j< n-1 ; j++)
             {
                     if(a[j] > a[j+1])
                     {
                             int temp = a[j];
                             a[j] = a[j+1];
                             a[j+1] = temp;

                     }
             }
     }
     
}
long getMaxNumber(int input[],int size)
{
     //I don't want to touch the original array.
     //Copy the elements into new array
     int a[size];
     for(int i = 0 ; i < size ; i++)
     {
           a[i] = input[i];
     } 
     sort(a,size); 
    
    //least element is not zero, i.e. zero is not present in the array.
    // Hence not divisible by 2 and 5 
    if(a[0] != 0 ) return -1;
     
     int rem[size];
     int rem_sum = 0;
     
     //populate all the reminders of digits into new array
     // Also trying to get the sum of reminder at the same time
     for(int i = 0; i < size ; i++)
     {
             rem_sum += (rem[i] = a[i]%3);         
     }
     
     // reminder that is in excess
     rem_sum %= 3;
     
    //stores the indices of digits in the array, that we are going to remove 
    int removed_index[2] = {-1,-1};

     if(rem_sum != 0)
     {
        int removed_rem_sum = 0;
        for(int i = 0 , j=0 ; i < size ; i++)
        { 
                if(rem[i] == rem_sum) // equal case
                {
                     removed_index[0] = i;
                     removed_index[1] = -1;
                     break;
                }
                else if(rem[i] > rem_sum) // greater case
                {
                     continue;
                }
                else if(removed_rem_sum != rem_sum && rem[i]!=0)//lesser case
                {
                     removed_index[j] = i;
                     removed_rem_sum += rem[i];
                     j++;
                }
          
        } //for loop
        
        //we were not able to remove anything
        //for example: in case the the digits are 0,5,8
        if(removed_index[0] == -1)
                            return 0;
     } //if rem_sum!=0

     long number = 0;
     for(int i = size-1 ; i > -1 ; i-- )
     {
             if(removed_index[0] != i && removed_index[1] != i)
             {
                number = number*10 + a[i];
             }
     }
      
     return number;          
                     
}