## Google Interview Question for Software Engineers

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

I found my mistake. I just have to return 0 instead of -1.

Comment hidden because of low score. Click to expand.
0
of 2 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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:

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")``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def max_num(digits):
dp = {0: 0}
for d in sorted(digits, reverse=True):
for q, v in list(dp.iteritems()):
v2 = 10 * v + d
q2 = v2 % 3
if q2 not in dp or dp[q2] < v2:
dp[q2] = v2
return dp[0]``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def max_num(digits):
dp = {0: 0}
for d in sorted(digits, reverse=True):
for q, v in list(dp.iteritems()):
v2 = 10 * v + d
q2 = v2 % 3
if q2 not in dp or dp[q2] < v2:
dp[q2] = v2
return dp[0]``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def max_num(digits):
dp = {0: 0}
for d in sorted(digits, reverse=True):
for _, v in list(dp.iteritems()):
v2 = 10 * v + d
q2 = v2 % 3
if q2 not in dp or dp[q2] < v2:
dp[q2] = v2
return dp[0]``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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
}else if(i%3==2){
// all numbers with reminder 2
}
}
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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

{
sort(_array.rbegin(), _array.rend());

makeDivisisbleByDivisor(_array);

return convertVectorToInt(_array);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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[:]``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package backtracking;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public static void main(String[] args) {
// TODO Auto-generated method stub

List<Integer> ls = new ArrayList<Integer>();
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)
else
{
}
}

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)
{
max=max/10;
}

}
else
{

}
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)
{
}

for(int i=start;i<input.size();i++)
{
combination(al,rl,i+1,target+input.get(i),input);
rl.remove(rl.size()-1);
}

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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 )
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)
subelements(al, set);
}
}

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;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ 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); }}
Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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>();
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>();
return result;
}
map.put(arr[i], i);
}
return null;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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++) {
}

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)
subelements(al, set);
}
}

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;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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(""));
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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(""));
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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(""));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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));

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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));

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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));

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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--;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

is this example only be soloved using data structures?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.