Google Interview Question Software Engineers
Country: United States
My working solution, I think this could be further optimized:
private static int getHigestNumDivisibleByThree(int[] arr) {
int sum = 0;
StringBuilder str = new StringBuilder();
Arrays.sort(arr);
for (int i = arr.length; i > 0; i--) {
sum = sum + arr[i - 1];
str.append(arr[i - 1]);
}
int remainder = sum % 3;
if (remainder == 0)
return Integer.parseInt(str.toString());
str = new StringBuilder();
boolean condition = true;
int removeNum = 0;
while (condition && remainder <= 9) {
if (contains(arr, remainder)) {
removeNum = remainder;
break;
}
remainder = remainder + 3;
}
if (removeNum == 0)
return 0;
for (int i = arr.length; i > 0; i--) {
if (removeNum == arr[i - 1]) {
continue;
}
str.append(arr[i - 1]);
}
return Integer.parseInt(str.toString());
}
private static boolean contains(int[] arr, int num) {
for (int i : arr)
if (i == num)
return true;
return false;
}
Simple backtracking will help
1. Sort the string (954311)
2. if sorted string is divided by 3, return the result.
3. remove one by one from the end and check if it is divisible by 3. In case of 954311, we start with removing last '1'. As 9431 is not divisible by 3 put the 1 back and do the same with same with next 1 and so on. You will realize only when you remove 5 you will get the rest of the number divisible by 3.
4. Concept is very similar to 8 queen problem but just here instead here the constraint is divisibility by 3.
Found a better solution:
Let's start with a element 'x'. Every element when you are adding to 'x' will either increase it by 1 or by 2 for sure right when doing mod by 3.Think about this.
Now all you have to do is to figure out which "bad" apples are causing the sum to be not divisible by 3.
sum of entire array mod 3 will let you know, how much offset you are from being divisible by 3. It can be either by 1 or by 2 right?
example 12331 sum of this is (1+2+3+3+1)%3=1
Now sort the entire array. This step is intuitive right? After that you just have to go from end to beginning figuring out which array element mod 3 is giving me the offset we calculated earlier.
You will also notice that maximum of 2 elements should be removed to make any digit greater than 2 to be divisible by 3. Right? As explained earlier, if you add any two random or same digits to existing sum the entire sum will be divisible by 3.
proof:
x + a + b
if x is not divisible by 3 then adding 'a' and adding 'b' will make it divisible by 3 because adding 'a' will increase the sum by either 0,1 or 2. and in all cases when adding 'a' and 'b' the entire sum becomes divisible by 3.
Code
def foo(a):
a = sorted([int(i) for i in a], reverse=True)
s = sum([int(i) for i in a])
if s%3 == 0:
return a
mod = s%3
n = len(a)
index_to_be_removed = []
#if no >= 3, there has to be answer
for i in range(2):
if index_to_be_removed:
break
for j in range(n-1, 0, -1):
if a[j]%3 == mod:
index_to_be_removed.append(j)
break
if i:
for k in range(j):
if not a[k]%3 or not a[j]%3:
continue
if (a[j] + a[k])%3 == mod:
index_to_be_removed.append(j)
index_to_be_removed.append(k)
for i in index_to_be_removed:
a = a[0:i]+a[i+1:]
print("".join([str(i) for i in a]))
foo("6532")
My solution is as follows,
public static String getLargestNumberDivisibleBy3(ArrayList<Integer> arrList){
PriorityQueue<Integer> bucket1 = new PriorityQueue<Integer>();
PriorityQueue<Integer> bucket2 = new PriorityQueue<Integer>();
for(Integer i:arrList){
if(i%3==1){
// all numbers with reminder 1
bucket1.add(i);
}else if(i%3==2){
// all numbers with reminder 2
bucket2.add(i);
}
}
while(arrList.size() >= 0 ){
int sum=0;
for(Integer i:arrList){
sum=sum+i;
}
if(sum%3==0){
break;
}else if(sum%3==1){
// if there is a number in bucket1 - chose the minimal else: take minimal from bucket 2
if(bucket1.size() > 0){
arrList.remove(bucket1.remove());
}else{
arrList.remove(bucket2.remove());
}
}else if(sum%3==2){
// if there is a number in bucket2 - chose the minimal else: take minimal from bucket 1
if(bucket2.size() > 0){
arrList.remove(bucket2.remove());
}else{
arrList.remove(bucket1.remove());
}
}
}
Collections.sort(arrList);
Collections.reverse(arrList);
StringBuilder str = new StringBuilder();
for(Integer i:arrList){
str.append(i);
}
if(str.toString().equals("")){
str.append("0");
}
return str.toString();
}
Some of the testcase,
i/p - 1,2,3,4,5,6,7,8,9,0
o/p - 9876543210
i/p - 2,5
o/p - 0
i/p - 3, 4, 0, 1, 5
o/p - 5430
package org.practice.test;
import java.util.List;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
public class FindSumOfThree {
public static void main(String[] args) {
int sum=0;
List<Integer> numberLst=Arrays.asList(3,1,4,1,9,3,5,2);
//Step 1: Sort the list
Collections.sort(numberLst,new Comparator<Integer>(){
@Override
public int compare(Integer arg0, Integer arg1) {
return arg1.compareTo(arg0);
}
});
// Step 2: Find the sum of list
sum=sumOfList(numberLst);
if(sum%3==0){
printLst(numberLst);
}else{
// Step3: remove the number from list to find sum divide by 3
int remove=divideFurtherByThree(numberLst);
for(int number:numberLst){
if(number!=remove){
System.out.print(number);
}
}
}
}
private static int sumOfList(List<Integer> numberLst){
int sum=0;
for(int number:numberLst){
sum=sum+number;
}
return sum;
}
private static int divideFurtherByThree(List<Integer> numberLst){
int removeNum=0;
for(int i=0;i<numberLst.size();i++){
int sum=0;
for(int j=0;j<numberLst.size();j++){
if(i!=j){
sum=sum+numberLst.get(j);
}else{
removeNum=numberLst.get(j);
}
}
if(sum%3==0){
return removeNum;
}
}
return 0;
}
private static void printLst(List<Integer> result){
for(int number:result){
System.out.print(number);
}
}
}
package org.practice.test;
import java.util.List;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
public class FindSumOfThree {
public static void main(String[] args) {
int sum=0;
List<Integer> numberLst=Arrays.asList(3,1,4,1,9,3,5,2);
//Step 1: Sort the list
Collections.sort(numberLst,new Comparator<Integer>(){
@Override
public int compare(Integer arg0, Integer arg1) {
return arg1.compareTo(arg0);
}
});
// Step 2: Find the sum of list
sum=sumOfList(numberLst);
if(sum%3==0)
printLst(numberLst);
else{
// Step3: remove the number from list to find sum divide by 3
int remove=divideFurtherByThree(numberLst);
for(int number:numberLst){
if(number!=remove){
System.out.print(number);
}
}
}
}
private static int sumOfList(List<Integer> numberLst){
int sum=0;
for(int number:numberLst){
sum=sum+number;
}
return sum;
}
private static int divideFurtherByThree(List<Integer> numberLst){
int removeNum=0;
for(int i=0;i<numberLst.size();i++){
int sum=0;
for(int j=0;j<numberLst.size();j++){
if(i!=j){
sum=sum+numberLst.get(j);
}else{
removeNum=numberLst.get(j);
}
}
if(sum%3==0)
return removeNum;
}
return 0;
}
private static void printLst(List<Integer> result){
for(int number:result){
System.out.print(number);
}
}
}
public class FindSumOfThree {
public static void main(String[] args) {
int sum=0;
List<Integer> numberLst=Arrays.asList(3,1,4,1,9,3,5,2);
//Step 1: Sort the list
Collections.sort(numberLst,new Comparator<Integer>(){
@Override
public int compare(Integer arg0, Integer arg1) {
return arg1.compareTo(arg0);
}
});
// Step 2: Find the sum of list
sum=sumOfList(numberLst);
if(sum%3==0)
printLst(numberLst);
else{
// Step3: remove the number from list to find sum divide by 3
int remove=divideFurtherByThree(numberLst);
for(int number:numberLst){
if(number!=remove){
System.out.print(number);
}
}
}
}
private static int sumOfList(List<Integer> numberLst){
int sum=0;
for(int number:numberLst){
sum=sum+number;
}
return sum;
}
private static int divideFurtherByThree(List<Integer> numberLst){
int removeNum=0;
for(int i=0;i<numberLst.size();i++){
int sum=0;
for(int j=0;j<numberLst.size();j++){
if(i!=j){
sum=sum+numberLst.get(j);
}else{
removeNum=numberLst.get(j);
}
}
if(sum%3==0)
return removeNum;
}
return 0;
}
private static void printLst(List<Integer> result){
for(int number:result){
System.out.print(number);
}}
}
This is my solution in C++
const int DIVISOR = 3;
unordered_map<int, list<int>> getModulos(const vector<int>& _array)
{
unordered_map<int, list<int>> modulos(DIVISOR);
for (int i = 0; i < (int)_array.size(); i++)//calculate each number in the array % 3 - result will always be 0, 1, or 2
{
int modulo = _array[i] % DIVISOR;
modulos[modulo].push_back(i); //store the index so it can be removed later
}
return modulos;
}
void makeDivisisbleByDivisor(vector<int>& _array)
{
unordered_map<int, list<int>> modulos = getModulos(_array);
//indicates the number (if any) that needs to be removed from the array in order to be divisible by 3
int moduloRemainder = ( modulos[1].size() + (modulos[2].size() * 2) ) % DIVISOR;
int index = 0;
if (modulos[moduloRemainder].empty()) //if we need to remove %2 but that array is empty remove 2 from %1
index = DIVISOR - moduloRemainder; //should always be 1...
else
index = moduloRemainder;
while (moduloRemainder > 0) //should execute a whopping 2 times max
{
int temp = modulos[index].back();
modulos[index].pop_back();
_array.erase(_array.begin() + temp);
moduloRemainder -= index;
}
}
//could probably utilize string stream but lazy
int convertVectorToInt(const vector<int>& _array)
{
int result = 0;
for (int i = 0; i < (int)_array.size(); i++)
result = (result * 10) + _array[i]; //multiply by ten to shift left
return result;
}
int answer(vector<int> _array)
{
sort(_array.rbegin(), _array.rend());
makeDivisisbleByDivisor(_array);
return convertVectorToInt(_array);
}
It is easy to think it is a largest number problem but it is not. For eg : List(9,6,3,0). largest number is 9630 which is divisible by 3. Like wise 3069 is divisible by 3. It is about taking a set of numbers and creating a subset which is divisible by 3. It is a subset sum problem and the subset sum should be divisible by 3.
A bit different approach.
1. get sum
1. if (sum % 3) = 0; return number
2. if (sum % 3) = 1; remove 1 or 4 or 7 return number
3. if (sum % 3) = 2; remove 2 or 5 or 8 return number
return 0
//C#
public static int GetMax3Divisible(int[] arr)
{
int[] digitCounts = GetDigitCounts(arr);
int sum = GetSum(arr);//get sum of digits
int rem = sum % 3;
if (rem == 1)
{//we have to remove 1 or 4 or 7 to get the number divisible by 3
if (!(RemoveNumber(digitCounts, 1) || RemoveNumber(digitCounts, 4)
|| RemoveNumber(digitCounts, 7)))//Note. Language should support Shortcircuit
{
return 0;
}
}
else if (rem == 2)
{//we have to remove 2 or 5 or 8 to get the number divisible by 3
if (!(RemoveNumber(digitCounts, 2) || RemoveNumber(digitCounts, 5)
|| RemoveNumber(digitCounts, 8)))//Note. Language should support Shortcircuit
{
return 0;
}
}
return GetNumber(digitCounts);
}
private static int[] GetDigitCounts(int[] arr)
{
//transfer the values to an array of digit counts
int[] digitCounts = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] >= 0 && (arr[i] < 10))
{
digitCounts[arr[i]]++;
}
else
{
throw new ArgumentOutOfRangeException();
}
}
return digitCounts;
}
private static Boolean RemoveNumber(int[] digitCounts, int number)
{
if (digitCounts[number] > 0)
{
digitCounts[number]--;
return true;
}
else if (number % 2 == 0)
{
number = number / 2;
if (digitCounts[number] > 1)
{ //remove 2 elements
digitCounts[number] = digitCounts[number] - 2;
}
return true;
}
return false;
}
private static int GetNumber(int[] digitCounts)
{
int number = 0;
for (int i = digitCounts.Length - 1; i >= 0; i--)
{
while (digitCounts[i]-- > 0 )
{
number = number * 10 + i;
}
}
return number;
}
private static int GetSum(int[] arr)
{
int sum = 0;
for (int i = 0; i < arr.Length; i++)
{
sum = sum + arr[i];
}
return sum;
}
public static void Test()
{
int[] a = { 2, 2, 4, 1,1};
Console.WriteLine("Number = {0}", GetMax3Divisible(a));
}
l,m=[i for i in raw_input()],[]
n=sorted([int(j) for j in l])[::-1]
if int(''.join([str(o) for o in n]))%3==0:
print int(''.join([str(o) for o in n]))
else:
for p in range(len(n)):
m.append(n.pop((len(n)-1)-p))
a=int(''.join([str(k) for k in n]))
if a%3==0:
q=sorted([int(r) for r in str(a)])
print ''.join([str(s) for s in q[::-1]])
else:
n.append(m[0])
del m[:]
package backtracking;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Google3Multiple {
public static void main(String[] args) {
// TODO Auto-generated method stub
List<Integer> ls = new ArrayList<Integer>();
ls.add(3);
ls.add(1);
ls.add(4);
ls.add(1);
ls.add(5);
ls.add(9);
List<Integer> al = findVal(ls);
System.out.print(al);
}
private static List findVal(List<Integer> ls)
{
List<Integer> rel = new ArrayList<Integer>();
List<Integer> temp = new ArrayList<Integer>();
for(Integer i:ls)
{
if(i%3!=0)
temp.add(i);
else
{
rel.add(i);
}
}
if(temp.size()!=0)
{
List<List<Integer>> al = new ArrayList<>();
List<Integer> rl = new ArrayList<>();
combination(al,rl,0,0,temp);
String [] res = new String[al.size()];
int c=0;
for(List<Integer> l:al)
{ StringBuffer sb = new StringBuffer();
for(int j:l){
sb.append(j);
}
res[c++]=sb.toString();
}
int max =-999;
for(int j=0;j<res.length;j++)
{
max=Math.max(max, Integer.parseInt(res[j]));
}
System.out.println(max);
while(max!=0)
{
rel.add(max%10);
max=max/10;
}
}
else
{
rel.addAll(ls);
}
Collections.sort(rel, Collections.reverseOrder());
return rel;
}
private static void combination(List<List<Integer>> al, List<Integer>rl, int start,int target,List<Integer> input)
{
if(target!=0 && target%3==0)
{
al.add(new ArrayList<>(rl));
}
for(int i=start;i<input.size();i++)
{
rl.add(input.get(i));
combination(al,rl,i+1,target+input.get(i),input);
rl.remove(rl.size()-1);
}
}
}
package career_cup;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;
public class ListOfNumbers {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("enter the list");
List<Integer> al = new ArrayList<Integer>();
for (int i = 0; i < 20; i++) {
int next = sc.nextInt();
if(next>0 && next <10 )
al.add(next);
else
break;
}
Collections.sort(al, Collections.reverseOrder());
Set<Integer> set = new TreeSet<Integer>(Collections.reverseOrder());
subelements(al, set);
int number=0;
int len =set.size();
Iterator<Integer> itr = set.iterator();
for (int i = 0; i < len; i++) {
number = itr.next();
if(number%3==0)
{
System.out.println("the result is " + number);
break;
}
else if (i== len-1){
System.out.println("the result is 0" );
break;
}
}
}
private static void subelements(List<Integer> al, Set<Integer> set) {
int rem = 0, number;
for (int i = 0; i < al.size(); i++) {
rem = al.remove(i);
number = number(al);
if (number > 0)
set.add(number);
subelements(al, set);
al.add(i,rem);
}
}
public static int number(List<Integer> al) {
int len = al.size(), sum = 0;
for (int i = 0; i < len; i++) {
sum += al.get(i) * Math.pow(10, len - 1 - i);
}
return sum;
}
}
var a = [3,1,4,1,5,9];
var max = 0;
var pattern = function(arr){
if(arr.length==1){
return arr;
}
var patterns = [];
for(var i=0;i<arr.length;i++){
debugger;
var copyArr = arr.slice(0,arr.length);
copyArr.splice(i,1)
var sub_patterns = pattern(copyArr);
for(var j=0;j<sub_patterns.length;j++){
var num = arr[i]*Math.pow(10,Math.floor(Math.log10(sub_patterns[j]))+1)+sub_patterns[j];
if(num%3 ==0 && num > max){
max = num;
}
patterns.push(num);
}
}
return patterns;
}
pattern(a);
console.log(max);
package google;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
public class LargestNumberDivisibleBy3 {
public static void main(String args[]) {
int[] input = { 3, 1, 1 };
System.out.println(getHigestNumDivisibleByThree(input));
}
private static int getHigestNumDivisibleByThree(int[] arr) {
int sum = 0;
StringBuilder str = new StringBuilder();
Arrays.sort(arr);
for (int i = arr.length; i > 0; i--) {
sum = sum + arr[i - 1];
str.append(arr[i - 1]);
}
int remainder = sum % 3;
if (remainder == 0)
return Integer.parseInt(str.toString());
str = new StringBuilder();
ArrayList<Integer> removeNum = new ArrayList<Integer>();
int remNumCount = 1;
while (remNumCount <= 2) {
remainder = sum % 3;
while (remainder <= 9 * remNumCount) {
removeNum = contains(arr, remainder, remNumCount);
if (removeNum != null) {
break;
}
remainder = remainder + 3;
}
remNumCount++;
}
if (removeNum == null)
return 0;
for (int i = 0; i < arr.length; i++) {
if (removeNum.contains(arr[i])) {
continue;
}
str.append(arr[i]);
}
return Integer.parseInt(str.toString());
}
private static ArrayList<Integer> contains(int[] arr, int num, int mode) {
if (mode == 1) {
for (int i : arr)
if (i == num) {
ArrayList<Integer> result = new ArrayList<Integer>();
result.add(i);
return result;
}
return null;
} else {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < arr.length; i++) {
if (map.containsKey(num - arr[i])) {
ArrayList<Integer> result = new ArrayList<Integer>();
result.add(arr[i]);
result.add(map.get(num - arr[i]));
return result;
}
map.put(arr[i], i);
}
return null;
}
}
}
package career_cup;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;
public class ListOfNumbers {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("enter the number of elements to be entered in the list");
int count = sc.nextInt();
List<Integer> al = new ArrayList<Integer>();
System.out.println("enter the list");
for (int i = 0; i < count; i++) {
al.add(sc.nextInt());
}
Collections.sort(al, Collections.reverseOrder());
Set<Integer> set = new TreeSet<Integer>(Collections.reverseOrder());
int num1 = number(al);
if (num1 % 3 == 0) {
System.out.println("the result is " + num1);
} else {
subelements(al, set);
int number = 0;
int len = set.size();
Iterator<Integer> itr = set.iterator();
for (int i = 0; i < len; i++) {
number = itr.next();
if (number % 3 == 0) {
System.out.println("the result is " + number);
break;
} else if (i == len - 1) {
System.out.println("the result is 0");
break;
}
}
}
}
private static void subelements(List<Integer> al, Set<Integer> set) {
int rem = 0, number;
for (int i = 0; i < al.size(); i++) {
rem = al.remove(i);
number = number(al);
if (number > 0)
set.add(number);
subelements(al, set);
al.add(i, rem);
}
}
public static int number(List<Integer> al) {
int len = al.size(), sum = 0;
for (int i = 0; i < len; i++) {
sum += al.get(i) * Math.pow(10, len - 1 - i);
}
return sum;
}
}
public static String formNumbers(int[] inputNumbers) {
int sum = getSum(inputNumbers);
List<Integer> integers = IntStream.of(inputNumbers).mapToObj(x -> x)
.sorted(Comparator.reverseOrder())
.collect(Collectors.toList());
int remainder = sum%3;
if (remainder == 0 ) {
return getResult(integers);
}
do {
if (integers.contains(remainder)){
integers.remove(Integer.valueOf(remainder));
sum = integers.stream().mapToInt(x-> x).sum();
remainder = sum%3;
if (remainder == 0 && integers.size() == 0) {
return "0";
} else {
return getResult(integers);
}
} else {
if (integers.size() > 0) {
int largeValue = integers.get(0);
if (largeValue < remainder) {
remainder--;
}else {
remainder = remainder + 3;
}
}
}
}while (sum > remainder);
return "0";
}
private static int getSum(int[] inputNumbers) {
return IntStream.of(inputNumbers).sum();
}
private static String getResult(List<Integer> integers) {
return integers.stream().map(String::valueOf).collect(Collectors.joining(""));
}
public static String formNumbers(int[] inputNumbers) {
int sum = getSum(inputNumbers);
List<Integer> integers = IntStream.of(inputNumbers).mapToObj(x -> x)
.sorted(Comparator.reverseOrder())
.collect(Collectors.toList());
int remainder = sum%3;
if (remainder == 0 ) {
return getResult(integers);
}
do {
if (integers.contains(remainder)){
integers.remove(Integer.valueOf(remainder));
sum = integers.stream().mapToInt(x-> x).sum();
remainder = sum%3;
if (remainder == 0 && integers.size() == 0) {
return "0";
} else {
return getResult(integers);
}
} else {
if (integers.size() > 0) {
int largeValue = integers.get(0);
if (largeValue < remainder) {
remainder--;
}else {
remainder = remainder + 3;
}
}
}
}while (sum > remainder);
return "0";
}
private static int getSum(int[] inputNumbers) {
return IntStream.of(inputNumbers).sum();
}
private static String getResult(List<Integer> integers) {
return integers.stream().map(String::valueOf).collect(Collectors.joining(""));
}
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class FormNumbersDivisibleBy3 {
public static void main(String[] args) {
System.out.println(formNumbers(new int[]{2,2}));
}
public static String formNumbers(int[] inputNumbers) {
int sum = getSum(inputNumbers);
List<Integer> integers = IntStream.of(inputNumbers).mapToObj(x -> x)
.sorted(Comparator.reverseOrder())
.collect(Collectors.toList());
int remainder = sum%3;
if (remainder == 0 ) {
return getResult(integers);
}
do {
if (integers.contains(remainder)){
integers.remove(Integer.valueOf(remainder));
sum = integers.stream().mapToInt(x-> x).sum();
remainder = sum%3;
if (remainder == 0 && integers.size() == 0) {
return "0";
} else {
return getResult(integers);
}
} else {
if (integers.size() > 0) {
int largeValue = integers.get(0);
if (largeValue < remainder) {
remainder--;
}else {
remainder = remainder + 3;
}
}
}
}while (sum > remainder);
return "0";
}
private static int getSum(int[] inputNumbers) {
return IntStream.of(inputNumbers).sum();
}
private static String getResult(List<Integer> integers) {
return integers.stream().map(String::valueOf).collect(Collectors.joining(""));
}
}
package com.my;
import java.util.Scanner;
/*
* You have L, a list containing some digits (0 to 9). Write a function answer(L) which finds
* the largest number that can be made from some or all of these digits and is divisible by 3.
* If it is not possible to make such a number, return 0 as the answer. L will contain anywhere
* from 1 to 9 digits. The same digit may appear multiple times in the list, but each element in
* the list may only be used once.
{{
Test cases
==========
Inputs:
(int list) l = [3, 1, 4, 1]
Output:
(int) 4311
Inputs:
(int list) l = [3, 1, 4, 1, 5, 9]
Output:
(int) 94311
*/
public class LargestNumberDevideBy3 {
/*
* Sort Array
* Add all elments of array
* check sum of array is devided by 3, if not get the mod value and search the value in array
* if it is there, the remove the element from and form largest number.
*
*/
private static String findLargestNumber(int a[]) {
quickSort(a, 0, a.length-1);
int sum = sumOfArray(a);
if((sum % 3) != 0) {
for(int i = 0; i < a.length; i++) {
for(int j = i; j < a.length; j++) {
if(a[j] != -1 && (sum - a[j]) % 3 == 0 ) {
sum = sum - a[j];
a[j] = -1;
break;
}
}
if(sum % 3 == 0) {
break;
}
sum = sum - a[i];
a[i] = -1;
}
}
String s = "";
for(int i = a.length-1; i >=0; i--) {
if(a[i] != -1) {
s += a[i];
}
}
return s;
}
private static int sumOfArray(int a[]) {
int sum = 0;
for(int i = 0 ; i < a.length; i++) {
sum += a[i];
}
return sum;
}
private static void quickSort(int a[], int low, int high) {
if(low < high) {
int value = partition(a, low, high);
quickSort(a, low, value - 1);
quickSort(a, value + 1, high);
}
}
private static int partition(int a[], int low, int high) {
//Find pivot -- pivot is the last element
int pivot = a[high];
//Make i value low - 1. if low is 0 then i value will be -1
int i = low -1;
for(int j = low; j <= high -1; j++) {
if(pivot >= a[j]) {
int temp = a[i+1];
a[i+1] = a[j];
a[j] = temp;
i++;
}
}
int temp = a[i+1];
a[i+1] = a[high];
a[high] = temp;
return i+1;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
int a[] = new int[m];
for (int i = 0; i < m; i++) {
a[i] = scanner.nextInt();
}
System.out.println(findLargestNumber(a));
}
}
package com.my;
import java.util.Scanner;
/*
* You have L, a list containing some digits (0 to 9). Write a function answer(L) which finds
* the largest number that can be made from some or all of these digits and is divisible by 3.
* If it is not possible to make such a number, return 0 as the answer. L will contain anywhere
* from 1 to 9 digits. The same digit may appear multiple times in the list, but each element in
* the list may only be used once.
{{
Test cases
==========
Inputs:
(int list) l = [3, 1, 4, 1]
Output:
(int) 4311
Inputs:
(int list) l = [3, 1, 4, 1, 5, 9]
Output:
(int) 94311
*/
public class LargestNumberDevideBy3 {
/*
* Sort Array
* Add all elments of array
* check sum of array is devided by 3, if not get the mod value and search the value in array
* if it is there, the remove the element from and form largest number.
*
*/
private static String findLargestNumber(int a[]) {
quickSort(a, 0, a.length-1);
int sum = sumOfArray(a);
if((sum % 3) != 0) {
for(int i = 0; i < a.length; i++) {
for(int j = i; j < a.length; j++) {
if(a[j] != -1 && (sum - a[j]) % 3 == 0 ) {
sum = sum - a[j];
a[j] = -1;
break;
}
}
if(sum % 3 == 0) {
break;
}
sum = sum - a[i];
a[i] = -1;
}
}
String s = "";
for(int i = a.length-1; i >=0; i--) {
if(a[i] != -1) {
s += a[i];
}
}
return s;
}
private static int sumOfArray(int a[]) {
int sum = 0;
for(int i = 0 ; i < a.length; i++) {
sum += a[i];
}
return sum;
}
private static void quickSort(int a[], int low, int high) {
if(low < high) {
int value = partition(a, low, high);
quickSort(a, low, value - 1);
quickSort(a, value + 1, high);
}
}
private static int partition(int a[], int low, int high) {
//Find pivot -- pivot is the last element
int pivot = a[high];
//Make i value low - 1. if low is 0 then i value will be -1
int i = low -1;
for(int j = low; j <= high -1; j++) {
if(pivot >= a[j]) {
int temp = a[i+1];
a[i+1] = a[j];
a[j] = temp;
i++;
}
}
int temp = a[i+1];
a[i+1] = a[high];
a[high] = temp;
return i+1;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
int a[] = new int[m];
for (int i = 0; i < m; i++) {
a[i] = scanner.nextInt();
}
System.out.println(findLargestNumber(a));
}
}
package com.my;
import java.util.Scanner;
/*
* You have L, a list containing some digits (0 to 9). Write a function answer(L) which finds
* the largest number that can be made from some or all of these digits and is divisible by 3.
* If it is not possible to make such a number, return 0 as the answer. L will contain anywhere
* from 1 to 9 digits. The same digit may appear multiple times in the list, but each element in
* the list may only be used once.
{{
Test cases
==========
Inputs:
(int list) l = [3, 1, 4, 1]
Output:
(int) 4311
Inputs:
(int list) l = [3, 1, 4, 1, 5, 9]
Output:
(int) 94311
*/
public class LargestNumberDevideBy3 {
/*
* Sort Array
* Add all elments of array
* check sum of array is devided by 3, if not get the mod value and search the value in array
* if it is there, the remove the element from and form largest number.
*
*/
private static String findLargestNumber(int a[]) {
quickSort(a, 0, a.length-1);
int sum = sumOfArray(a);
if((sum % 3) != 0) {
for(int i = 0; i < a.length; i++) {
for(int j = i; j < a.length; j++) {
if(a[j] != -1 && (sum - a[j]) % 3 == 0 ) {
sum = sum - a[j];
a[j] = -1;
break;
}
}
if(sum % 3 == 0) {
break;
}
sum = sum - a[i];
a[i] = -1;
}
}
String s = "";
for(int i = a.length-1; i >=0; i--) {
if(a[i] != -1) {
s += a[i];
}
}
return s;
}
private static int sumOfArray(int a[]) {
int sum = 0;
for(int i = 0 ; i < a.length; i++) {
sum += a[i];
}
return sum;
}
private static void quickSort(int a[], int low, int high) {
if(low < high) {
int value = partition(a, low, high);
quickSort(a, low, value - 1);
quickSort(a, value + 1, high);
}
}
private static int partition(int a[], int low, int high) {
//Find pivot -- pivot is the last element
int pivot = a[high];
//Make i value low - 1. if low is 0 then i value will be -1
int i = low -1;
for(int j = low; j <= high -1; j++) {
if(pivot >= a[j]) {
int temp = a[i+1];
a[i+1] = a[j];
a[j] = temp;
i++;
}
}
int temp = a[i+1];
a[i+1] = a[high];
a[high] = temp;
return i+1;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
int a[] = new int[m];
for (int i = 0; i < m; i++) {
a[i] = scanner.nextInt();
}
System.out.println(findLargestNumber(a));
}
}
public class LargestNumberDevideBy3 {
/*
* Sort Array
* Add all elments of array
* check sum of array is devided by 3, if not get the mod value and search the value in array
* if it is there, the remove the element from and form largest number.
*
*/
private static String findLargestNumber(int a[]) {
quickSort(a, 0, a.length-1);
int sum = sumOfArray(a);
if((sum % 3) != 0) {
for(int i = 0; i < a.length; i++) {
for(int j = i; j < a.length; j++) {
if(a[j] != -1 && (sum - a[j]) % 3 == 0 ) {
sum = sum - a[j];
a[j] = -1;
break;
}
}
if(sum % 3 == 0) {
break;
}
sum = sum - a[i];
a[i] = -1;
}
}
String s = "";
for(int i = a.length-1; i >=0; i--) {
if(a[i] != -1) {
s += a[i];
}
}
return s;
}
private static int sumOfArray(int a[]) {
int sum = 0;
for(int i = 0 ; i < a.length; i++) {
sum += a[i];
}
return sum;
}
private static void quickSort(int a[], int low, int high) {
if(low < high) {
int value = partition(a, low, high);
quickSort(a, low, value - 1);
quickSort(a, value + 1, high);
}
}
private static int partition(int a[], int low, int high) {
//Find pivot -- pivot is the last element
int pivot = a[high];
//Make i value low - 1. if low is 0 then i value will be -1
int i = low -1;
for(int j = low; j <= high -1; j++) {
if(pivot >= a[j]) {
int temp = a[i+1];
a[i+1] = a[j];
a[j] = temp;
i++;
}
}
int temp = a[i+1];
a[i+1] = a[high];
a[high] = temp;
return i+1;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
int a[] = new int[m];
for (int i = 0; i < m; i++) {
a[i] = scanner.nextInt();
}
System.out.println(findLargestNumber(a));
}
}
reference Python thoughts from @americano
import java.util.*;
import java.lang.*;
public class LargestDivisableBy3 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] nums = new int[]{4,5,2,4,1,1,1,8};
System.out.println(getLargestDivisableBy3(nums));
}
public static int getLargestDivisableBy3(int[] digits){
Arrays.sort(digits);
reverse(digits);
Map<Integer,Integer> map = new HashMap<>();
map.put(0,0);
for(int i=0;i<digits.length;i++){
Map<Integer,Integer> tempMap = new HashMap<>(map);
for(int key:map.keySet()){
int value = map.get(key);
int temp = value*10+digits[i];
int r = temp%3;
if(!tempMap.containsKey(r)){
tempMap.put(r,temp);
}else if(tempMap.get(r)<temp){
tempMap.put(r,temp);
}
}
map = tempMap;
}
return map.get(0);
}
public static void reverse(int[] array){
int i=0;
int j=array.length-1;
while(i<j){
int t = array[i];
array[i] = array[j];
array[j] = t;
i++;
j--;
}
}
}
Easy Java solution:
private int largestNumberDivBy3_noRecursion(List<Integer> list) {
if (list.isEmpty()) {
return 0;
}
// sort the numbers
Collections.sort(list);
Collections.reverse(list);
StringBuilder sb = new StringBuilder();
for (int i : list) {
sb.append(i);
}
int end = sb.length() - 1;
StringBuilder word = sb;
while (sb.length() > 0) {
int num = Integer.parseInt(sb.toString());
if (num % 3 == 0) return num;
if (end < 0) {
// remove the last char and reset the 'end'
word = word.deleteCharAt(word.length() - 1);
end = word.length() - 1;
}
sb = new StringBuilder(word);
sb = sb.deleteCharAt(end);
end --;
}
return 0;
}
here is the typescript answer O(N)
calculate(){
let list = this.inputValue.split(',').map(i => +i);
list = list.sort((a,b)=> b > a? 1: -1 );
this.sum = list.reduce((prev, curr) => prev + curr)
this.reminder = this.sum % 3;
if(this.reminder !== 0) {
for(var i = list.length - 1; i >= 0 ; i--) {
if(list[i] % 3 === this.reminder) {
list[i] = -1;
break;
}
}
if(list.some(l => l === -1)) {
list = list.filter(l => l != -1);
} else {
var counter = 0;
for(var i = list.length - 1; i >= 0 ; i--) {
if(list[i] % 3 === (this.reminder % 2 + 1)) {
list[i] = -1;
counter++;
}
if(counter == 2) {
break;
}
}
list = list.filter(l => l != -1);
}
}
if(list.length > 0) {
this.name = +(list.join(''));
} else {
this.name = 0;
}
}
I found my mistake. I just have to return 0 instead of -1.
- Parth Patel February 22, 2017