Created
July 19, 2014 01:59
-
-
Save pavelnganpi/899a52793dc58d62e0bc to your computer and use it in GitHub Desktop.
Given an array of non-negative integers. Find the largest multiple of 3 that can be formed from array elements. For example, if the input array is {8, 1, 9}, the output should be “9 8 1″, and if the input array is {8, 1, 7, 6, 0}, output should be “8 7 6 0″.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package test; | |
import java.util.ArrayList; | |
import java.util.Collections; | |
import java.util.LinkedList; | |
import java.util.List; | |
import java.util.Queue; | |
public class LargeMultipleThree { | |
//method to loas the list when queues are dequeued | |
public static void loadAux(List<Integer> aux,Queue<?> q,Queue<?> q1, Queue<?> q2){ | |
while(!q.isEmpty()){ | |
aux.add((Integer) q.remove()); | |
} | |
while(!q1.isEmpty()){ | |
aux.add((Integer) q1.remove()); | |
} | |
while(!q2.isEmpty()){ | |
aux.add((Integer) q2.remove()); | |
} | |
} | |
public static int solution(int[] arr){ | |
//create 3 queues | |
Queue<Integer> q = new LinkedList<Integer>(); | |
Queue<Integer> q1 = new LinkedList<Integer>(); | |
Queue<Integer> q2 = new LinkedList<Integer>(); | |
int sum = 0; | |
//scan through array getting the sum | |
for (int i = 0; i<arr.length;i++){ | |
sum = sum + arr[i]; | |
//checks if each digit has a remainder of 0 modulus 3 | |
//then adds it to q | |
if(arr[i]%3 == 0){ | |
q.add(arr[i]); | |
} | |
//checks if each digit has a remainder of 1 modulus 3 | |
else if(arr[i]%3 ==1){ | |
q1.add(arr[i]); | |
} | |
else{ | |
q2.add(arr[i]); | |
} | |
} | |
if(sum%3 == 1){ | |
if(!q1.isEmpty()){ ////if sum mod 3 is 1 remove first element in q1 | |
q1.remove(); | |
} | |
else{// remove 2 elements from q2, otherewise number is not a multiple of 3 | |
if(!q2.isEmpty()){ | |
q2.remove(); | |
} | |
else{ | |
return 0; | |
} | |
if(!q2.isEmpty()){ | |
q2.remove(); | |
} | |
else{ | |
return 0; | |
} | |
} | |
} | |
if(sum%3 == 2){ | |
if(!q2.isEmpty()){ | |
q2.remove(); | |
} | |
else{ | |
if(!q1.isEmpty()){ | |
q1.remove(); | |
} | |
else{ | |
return 0; | |
} | |
if(!q1.isEmpty()){ | |
q1.remove(); | |
} | |
else{ | |
return 0; | |
} | |
} | |
} | |
List<Integer> aux = new ArrayList<Integer>(); | |
loadAux(aux, q, q1, q2); | |
//sorts the list | |
Collections.sort(aux); | |
//reverses the list | |
Collections.reverse(aux); | |
for(int i=0;i<aux.size();i++){ | |
System.out.println(aux.toString()); | |
} | |
return 1; | |
} | |
public static void main(String[]args){ | |
int[] test = {8,1,7,6,0}; | |
solution(test); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
this problem almost ok but i want to see some more improvements
Fill 3 queusrs
q0 elments which give 0 when take modulo with 3
q1 elements which give 1
q2 elements which give 2
now sort all these queue in decreasing order
if sum is 0 then just sort main queue
if sum give 1 as modulo then if q1 is not empty remove 1 element fron tail side
else if sum give 1 as module and q1 is empty remove two least element from q2
note:- if q2 not have 2 elements then we cannot make a no multiple of 3 handle this also
same way if remoinder is 2
remove 1 least element from q2 if q2 is empty then remove 2 least element from q1 and if q1 not have 2 element then we cannot make a no multiple of 3.....