Problem#
Given an array of digits digits, return the largest multiple of three that can be formed by concatenating some of the given digits in any order . If there is no answer return an empty string.
Since the answer may not fit in an integer data type, return the answer as a string. Note that the returning answer must not contain unnecessary leading zeros.
Examples#
Example 1#
1
2
Input: digits = [ 8 , 1 , 9 ]
Output: "981"
Example 2#
1
2
Input: digits = [ 8 , 6 , 7 , 1 , 0 ]
Output: "8760"
Example 3#
1
2
Input: digits = [ 1 ]
Output: ""
Constraints#
1 <= digits.length <= 10^40 <= digits[i] <= 9
Solution#
Method 1 – Greedy and Counting#
Intuition#
To form the largest multiple of three, we need the sum of digits to be divisible by 3. We can remove the minimal number of digits (with smallest values) to achieve this, and then sort the remaining digits in descending order for the largest number.
Approach#
Count digits by their remainder modulo 3.
Compute the total sum modulo 3.
If sum % 3 == 1, remove one digit with remainder 1, or two digits with remainder 2.
If sum % 3 == 2, remove one digit with remainder 2, or two digits with remainder 1.
If not possible, return empty string.
Sort remaining digits in descending order and join.
Remove leading zeros, if all digits are zero, return “0”.
Code#
Cpp
Go
Java
Kotlin
Python
Rust
Typescript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public :
string largestMultipleOfThree(vector< int >& digits) {
vector< int > cnt(10 , 0 );
int sum = 0 ;
for (int d : digits) cnt[d]++ , sum += d;
auto remove = [& ](int r, int times) {
for (int i = 0 ; i < times; ++ i) {
for (int d = 0 ; d < 10 ; ++ d) {
if (cnt[d] && d % 3 == r) {
cnt[d]-- ;
break ;
}
}
}
};
if (sum % 3 == 1 ) {
if (! remove(1 , 1 )) remove(2 , 2 );
} else if (sum % 3 == 2 ) {
if (! remove(2 , 1 )) remove(1 , 2 );
}
string ans;
for (int d = 9 ; d >= 0 ; -- d) ans += string(cnt[d], '0' + d);
if (ans.empty()) return "" ;
if (ans[0 ] == '0' ) return "0" ;
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
func largestMultipleOfThree (digits []int ) string {
cnt := make([]int , 10 )
sum := 0
for _ , d := range digits {
cnt [d ]++
sum += d
}
remove := func (r , times int ) bool {
for i := 0 ; i < times ; i ++ {
for d := 0 ; d < 10 ; d ++ {
if cnt [d ] > 0 && d % 3 == r {
cnt [d ]--
goto next
}
}
return false
next :
}
return true
}
if sum % 3 == 1 {
if !remove (1 , 1 ) && !remove (2 , 2 ) {
return ""
}
} else if sum % 3 == 2 {
if !remove (2 , 1 ) && !remove (1 , 2 ) {
return ""
}
}
ans := ""
for d := 9 ; d >= 0 ; d -- {
for i := 0 ; i < cnt [d ]; i ++ {
ans += fmt .Sprintf ("%d" , d )
}
}
if len(ans ) == 0 {
return ""
}
if ans [0 ] == '0' {
return "0"
}
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public String largestMultipleOfThree (int [] digits) {
int [] cnt = new int [ 10] ;
int sum = 0;
for (int d : digits) { cnt[ d]++ ; sum += d; }
boolean removed = false ;
if (sum % 3 == 1) {
removed = remove(cnt, 1, 1);
if (! removed) removed = remove(cnt, 2, 2);
} else if (sum % 3 == 2) {
removed = remove(cnt, 2, 1);
if (! removed) removed = remove(cnt, 1, 2);
}
StringBuilder ans = new StringBuilder();
for (int d = 9; d >= 0; d-- ) {
for (int i = 0; i < cnt[ d] ; i++ ) ans.append (d);
}
if (ans.length () == 0) return "" ;
if (ans.charAt (0) == '0' ) return "0" ;
return ans.toString ();
}
private boolean remove (int [] cnt, int r, int times) {
for (int i = 0; i < times; i++ ) {
boolean found = false ;
for (int d = 0; d < 10; d++ ) {
if (cnt[ d] > 0 && d % 3 == r) {
cnt[ d]-- ;
found = true ;
break ;
}
}
if (! found) return false ;
}
return true ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
fun largestMultipleOfThree (digits: IntArray): String {
val cnt = IntArray(10 )
var sum = 0
for (d in digits) { cnt[d]++ ; sum += d }
fun remove (r: Int, times: Int): Boolean {
repeat(times) {
for (d in 0. .9 ) {
if (cnt[d] > 0 && d % 3 == r) {
cnt[d]--
return @repeat
}
}
return false
}
return true
}
if (sum % 3 == 1 ) {
if (!remove(1 , 1 )) remove(2 , 2 )
} else if (sum % 3 == 2 ) {
if (!remove(2 , 1 )) remove(1 , 2 )
}
val ans = StringBuilder()
for (d in 9 downTo 0 ) repeat(cnt[d]) { ans.append(d) }
if (ans.isEmpty()) return ""
if (ans[0 ] == '0' ) return "0"
return ans.toString()
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def largestMultipleOfThree (digits: list[int]) -> str:
cnt = [0 ]* 10
s = sum(digits)
for d in digits:
cnt[d] += 1
def remove (r: int, times: int) -> bool:
for _ in range(times):
for d in range(10 ):
if cnt[d] and d % 3 == r:
cnt[d] -= 1
break
else :
return False
return True
if s % 3 == 1 :
if not remove(1 , 1 ):
if not remove(2 , 2 ):
return ""
elif s % 3 == 2 :
if not remove(2 , 1 ):
if not remove(1 , 2 ):
return ""
ans = '' . join(str(d)* cnt[d] for d in range(9 , - 1 , - 1 ))
if not ans:
return ""
if ans[0 ] == '0' :
return "0"
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
impl Solution {
pub fn largest_multiple_of_three (digits: Vec< i32 > ) -> String {
let mut cnt = [0 ; 10 ];
let mut sum = 0 ;
for & d in & digits {
cnt[d as usize ] += 1 ;
sum += d;
}
let mut remove = | r: i32 , times: i32 | {
for _ in 0 .. times {
let mut found = false ;
for d in 0 .. 10 {
if cnt[d] > 0 && d as i32 % 3 == r {
cnt[d] -= 1 ;
found = true ;
break ;
}
}
if ! found { return false ; }
}
true
};
if sum % 3 == 1 {
if ! remove(1 , 1 ) && ! remove(2 , 2 ) {
return "" .to_string();
}
} else if sum % 3 == 2 {
if ! remove(2 , 1 ) && ! remove(1 , 2 ) {
return "" .to_string();
}
}
let mut ans = String::new();
for d in (0 .. 10 ).rev() {
for _ in 0 .. cnt[d] {
ans.push((b '0' + d as u8 ) as char );
}
}
if ans.is_empty() { return "" .to_string(); }
if ans.chars().next().unwrap() == '0' { return "0" .to_string(); }
ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
largestMultipleOfThree (digits : number []): string {
const cnt = Array(10 ).fill (0 );
let sum = 0 ;
for (const d of digits ) { cnt [d ]++ ; sum += d ; }
function remove (r : number , times : number ): boolean {
for (let i = 0 ; i < times ; i ++ ) {
let found = false ;
for (let d = 0 ; d < 10 ; d ++ ) {
if (cnt [d ] > 0 && d % 3 === r ) {
cnt [d ]-- ;
found = true ;
break ;
}
}
if (! found ) return false ;
}
return true ;
}
if (sum % 3 === 1 ) {
if (! remove (1 , 1 )) remove (2 , 2 );
} else if (sum % 3 === 2 ) {
if (! remove (2 , 1 )) remove (1 , 2 );
}
let ans = '' ;
for (let d = 9 ; d >= 0 ; d -- ) ans += String(d ).repeat (cnt [d ]);
if (! ans ) return '' ;
if (ans [0 ] === '0' ) return '0' ;
return ans ;
}
}
Complexity#
⏰ Time complexity: O(n), since we process each digit and sort/count.
🧺 Space complexity: O(1), only a constant number of counters are used.