# Find the largest multiple of 3 from array of digits | Set 2 (In O(n) time and O(1) space)

• Difficulty Level : Hard
• Last Updated : 01 Dec, 2021

Given an array of digits (contain elements from 0 to 9). Find the largest number that can be made from some or all digits of array and is divisible by 3. The same element may appear multiple times in the array, but each element in the array may only be used once.
Examples:

```Input : arr[] = {5, 4, 3, 1, 1}
Output : 4311

Input : Arr[] = {5, 5, 5, 7}
Output : 555 ```

We have discussed a queue based solution. Both solutions (discussed in previous and this posts) are based on the fact that a number is divisible by 3 if and only if sum of digits of the number is divisible by 3.
For example, let us consider 555, it is divisible by 3 because sum of digits is 5 + 5 + 5 = 15, which is divisible by 3. If a sum of digits is not divisible by 3 then the remainder should be either 1 or 2.
If we get remainder either ‘1’ or ‘2’, we have to remove maximum two digits to make a number that is divisible by 3:

1. If remainder is ‘1’ : We have to remove single digit that have remainder ‘1’ or we have to remove two digit that have remainder ‘2’ ( 2 + 2 => 4 % 3 => ‘1’)
2. If remainder is ‘2’ : .We have to remove single digit that have remainder ‘2’ or we have to remove two digit that have remainder ‘1’ ( 1 + 1 => 2 % 3 => 2 ).

Examples :

```Input : arr[] = 5, 5, 5, 7
Sum of digits = 5 + 5 + 5 + 7 = 22
Remainder = 22 % 3 = 1
We remove smallest single digit that
has remainder '1'. We remove 7 % 3 = 1
So largest number divisible by 3 is : 555

Let's take an another example :
Input : arr[]  = 4 , 4 , 1 , 1 , 1 , 3
Sum of digits  = 4 + 4 + 1 + 1 + 1 + 3 = 14
Reminder = 14 % 3 = 2
We have to remove the smallest digit that
has remainder ' 2 ' or two digits that have
remainder '1'. Here there is no digit with
reminder '2', so we have to remove two smallest
digits that have remainder '1'. The digits are :
1, 1. So largest number divisible by 3 is 4 4 3 1 ```

Below are implementation of above idea.

## C++

 `// C++ program to find the largest number``// that can be mode from elements of the``// array and is divisible by 3``#include``using` `namespace` `std;`` ` `// Number of digits``#define MAX_SIZE 10`` ` `// function to sort array of digits using``// counts``void` `sortArrayUsingCounts(``int` `arr[], ``int` `n)``{``    ``// Store count of all elements``    ``int` `count[MAX_SIZE] = {0};``    ``for` `(``int` `i = 0; i < n; i++)``        ``count[arr[i]]++;`` ` `    ``// Store``    ``int` `index = 0;``    ``for` `(``int` `i = 0; i < MAX_SIZE; i++)``        ``while` `(count[i] > 0)``            ``arr[index++] = i, count[i]--;``}`` ` `// Remove elements from arr[] at indexes ind1 and ind2``bool` `removeAndPrintResult(``int` `arr[], ``int` `n, ``int` `ind1,``                                        ``int` `ind2 = -1)``{``    ``for` `(``int` `i = n-1; i >=0; i--)``        ``if` `(i != ind1 && i != ind2)``            ``cout << arr[i] ;``}`` ` `// Returns largest multiple of 3 that can be formed``// using arr[] elements.``bool` `largest3Multiple(``int` `arr[], ``int` `n)``{``    ``// Sum of all array element``    ``int` `sum = accumulate(arr, arr+n, 0);`` ` `     ` `    ``// Sort array element in increasing order``    ``sortArrayUsingCounts(arr, n);``   ` `    ``// Sum is divisible by 3 , no need to``    ``// delete an element``    ``if` `(sum%3 == 0)``    ``{  ``          ``removeAndPrintResult(arr,n,-1,-1);``          ``return` `true` `;``    ``}`` ` `    ``// Find reminder``    ``int` `remainder = sum % 3;`` ` `    ``// If remainder is '1', we have to delete either``    ``// one element of remainder '1' or two elements``    ``// of remainder '2'``    ``if` `(remainder == 1)``    ``{``        ``int` `rem_2;``        ``rem_2 = -1, rem_2 = -1;`` ` `        ``// Traverse array elements``        ``for` `(``int` `i = 0 ; i < n ; i++)``        ``{``            ``// Store first element of remainder '1'``            ``if` `(arr[i]%3 == 1)``            ``{``                ``removeAndPrintResult(arr, n, i);``                ``return` `true``;``            ``}`` ` `            ``if` `(arr[i]%3 == 2)``            ``{``                ``// If this is first occurrence of remainder 2``                ``if` `(rem_2 == -1)``                    ``rem_2 = i;`` ` `                ``// If second occurrence``                ``else` `if` `(rem_2 == -1)``                    ``rem_2 = i;``            ``}``        ``}`` ` `        ``if` `(rem_2 != -1 && rem_2 != -1)``        ``{``            ``removeAndPrintResult(arr, n, rem_2, rem_2);``            ``return` `true``;``        ``}``    ``}`` ` `    ``// If remainder is '2', we have to delete either``    ``// one element of remainder '2' or two elements``    ``// of remainder '1'``    ``else` `if` `(remainder == 2)``    ``{``        ``int` `rem_1;``        ``rem_1 = -1, rem_1 = -1;`` ` `        ``// traverse array elements``        ``for` `(``int` `i = 0; i < n; i++)``        ``{``            ``// store first element of remainder '2'``            ``if` `(arr[i]%3 == 2)``            ``{``                ``removeAndPrintResult(arr, n, i);``                ``return` `true``;``            ``}`` ` `            ``if` `(arr[i]%3 == 1)``            ``{``                ``// If this is first occurrence of remainder 1``                ``if` `(rem_1 == -1)``                    ``rem_1 = i;`` ` `                ``// If second occurrence``                ``else` `if` `(rem_1 == -1)``                    ``rem_1 = i;``            ``}``        ``}`` ` `        ``if` `(rem_1 != -1 && rem_1 != -1)``        ``{``            ``removeAndPrintResult(arr, n, rem_1, rem_1);``            ``return` `true``;``        ``}``    ``}`` ` `    ``cout << ``"Not possible"``;``    ``return` `false``;``}`` ` `// Driver code``int` `main()``{``    ``int` `arr[] = {4, 4, 1, 1, 1, 3 } ;``    ``int` `n = ``sizeof``(arr)/``sizeof``(arr);``    ``largest3Multiple(arr, n);``    ``return` `0;``}`

## Java

 `// Java program to find the largest number``// that can be mode from elements of the``// array and is divisible by 3``import` `java.util.*;`` ` `class` `GFG ``{`` ` `    ``// Number of digits``    ``static` `int` `MAX_SIZE = ``10``;`` ` `    ``// function to sort array of digits using``    ``// counts``    ``static` `void` `sortArrayUsingCounts(``int` `arr[], ``                                     ``int` `n)``    ``{``        ``// Store count of all elements``        ``int``[] count = ``new` `int``[MAX_SIZE];``        ``for` `(``int` `i = ``0``; i < n; i++) ``        ``{``            ``count[arr[i]]++;``        ``}`` ` `        ``// Store``        ``int` `index = ``0``;``        ``for` `(``int` `i = ``0``; i < MAX_SIZE; i++) ``        ``{``            ``while` `(count[i] > ``0``) ``            ``{``                ``arr[index++] = i;``                ``count[i]--;``            ``}``        ``}``    ``}`` ` `    ``// Remove elements from arr[]``    ``// at indexes ind1 and ind2``    ``static` `void` `removeAndPrintResult(``int` `arr[], ``int` `n, ``                                     ``int` `ind1, ``int` `ind2)``    ``{``        ``for` `(``int` `i = n - ``1``; i >= ``0``; i--)``        ``{``            ``if` `(i != ind1 && i != ind2) ``            ``{``                ``System.out.print(arr[i]);``            ``}``        ``}``    ``}`` ` `    ``// Returns largest multiple of 3 ``    ``// that can be formed using``    ``// arr[] elements.``    ``static` `boolean` `largest3Multiple(``int` `arr[], ``                                    ``int` `n)``    ``{``        ``// Sum of all array element``        ``int` `sum = accumulate(arr, ``0``, n);``         ` `        ``// Sort array element in increasing order``        ``sortArrayUsingCounts(arr, n);``         ` `        ``// If sum is divisible by 3, ``        ``// no need to delete an element``        ``if` `(sum % ``3` `== ``0``) ``        ``{``            ``removeAndPrintResult(arr, n, -``1``, -``1``);``            ``return` `true``;``        ``}`` ` `        ``// Find reminder``        ``int` `remainder = sum % ``3``;`` ` `        ``// If remainder is '1', we have to ``        ``// delete either one element of ``        ``// remainder '1' or two elements of ``        ``// remainder '2'``        ``if` `(remainder == ``1``)``        ``{``            ``int``[] rem_2 = ``new` `int``[``2``];``            ``rem_2[``0``] = -``1``;``            ``rem_2[``1``] = -``1``;`` ` `            ``// Traverse array elements``            ``for` `(``int` `i = ``0``; i < n; i++) ``            ``{``                 ` `                ``// Store first element of remainder '1'``                ``if` `(arr[i] % ``3` `== ``1``)``                ``{``                    ``removeAndPrintResult(arr, n, i, -``1``);``                    ``return` `true``;``                ``}`` ` `                ``if` `(arr[i] % ``3` `== ``2``)``                ``{``                     ` `                    ``// If this is first occurrence``                    ``// of remainder 2``                    ``if` `(rem_2[``0``] == -``1``)``                    ``{``                        ``rem_2[``0``] = i;``                    ``}``                     ` `                    ``// If second occurrence``                    ``else` `if` `(rem_2[``1``] == -``1``) ``                    ``{``                        ``rem_2[``1``] = i;``                    ``}``                ``}``            ``}`` ` `            ``if` `(rem_2[``0``] != -``1` `&& ``                ``rem_2[``1``] != -``1``) ``            ``{``                ``removeAndPrintResult(arr, n, rem_2[``0``], ``                                             ``rem_2[``1``]);``                ``return` `true``;``            ``}``        ``} ``         ` `        ``// If remainder is '2', we have to ``        ``// delete either one element of ``        ``// remainder '2' or two elements of``        ``// remainder '1'``        ``else` `if` `(remainder == ``2``) ``        ``{``            ``int``[] rem_1 = ``new` `int``[``2``];``            ``rem_1[``0``] = -``1``;``            ``rem_1[``1``] = -``1``;`` ` `            ``// traverse array elements``            ``for` `(``int` `i = ``0``; i < n; i++) ``            ``{``                 ` `                ``// store first element of remainder '2'``                ``if` `(arr[i] % ``3` `== ``2``) ``                ``{``                    ``removeAndPrintResult(arr, n, i, -``1``);``                    ``return` `true``;``                ``}`` ` `                ``if` `(arr[i] % ``3` `== ``1``) ``                ``{``                     ` `                    ``// If this is first occurrence``                    ``// of remainder 1``                    ``if` `(rem_1[``0``] == -``1``) ``                    ``{``                        ``rem_1[``0``] = i;``                    ``} ``                     ` `                    ``// If second occurrence``                    ``else` `if` `(rem_1[``1``] == -``1``) ``                    ``{``                        ``rem_1[``1``] = i;``                    ``}``                ``}``            ``}`` ` `            ``if` `(rem_1[``0``] != -``1` `&& ``                ``rem_1[``1``] != -``1``)``            ``{``                ``removeAndPrintResult(arr, n, rem_1[``0``], ``                                             ``rem_1[``1``]);``                ``return` `true``;``            ``}``        ``}``        ``System.out.print(``"Not possible"``);``        ``return` `false``;``    ``}`` ` `    ``static` `int` `accumulate(``int``[] arr,``                          ``int` `start, ``                          ``int` `end) ``    ``{``        ``int` `sum = ``0``;``        ``for` `(``int` `i = ``0``; i < arr.length; i++) ``        ``{``            ``sum += arr[i];``        ``}``        ``return` `sum;``    ``}``     ` `    ``// Driver code``    ``public` `static` `void` `main(String[] args)``    ``{``        ``int` `arr[] = {``4``, ``4``, ``1``, ``1``, ``1``, ``3``};``        ``int` `n = arr.length;``        ``largest3Multiple(arr, n);``    ``}``}`

## Python3

 `# Python3 program to find the largest number``# that can be mode from elements of the``# array and is divisible by 3`` ` `# Number of digits``MAX_SIZE ``=` `10`` ` `# function to sort array of digits using``# counts``def` `sortArrayUsingCounts(arr, n):`` ` `    ``# Store count of all elements``    ``count ``=` `[``0``]``*``MAX_SIZE``    ``for` `i ``in` `range``(n):``        ``count[arr[i]] ``+``=` `1`` ` `    ``# Store``    ``index ``=` `0``    ``for` `i ``in` `range``(MAX_SIZE):``        ``while` `count[i] > ``0``:``            ``arr[index] ``=` `i``            ``index ``+``=` `1``            ``count[i] ``-``=` `1`` ` ` ` `# Remove elements from arr[] at indexes ind1 and ind2``def` `removeAndPrintResult(arr, n, ind1, ind2``=``-``1``):``    ``for` `i ``in` `range``(n``-``1``, ``-``1``, ``-``1``):``        ``if` `i !``=` `ind1 ``and` `i !``=` `ind2:``            ``print``(arr[i], end``=``"")`` ` ` ` `# Returns largest multiple of 3 that can be formed``# using arr[] elements.``def` `largest3Multiple(arr, n):`` ` `    ``# Sum of all array element``    ``s ``=` `sum``(arr)`` ` `    ``# Sort array element in increasing order``    ``sortArrayUsingCounts(arr, n)`` ` `    ``# Sum is divisible by 3, no need to``    ``# delete an element``    ``if` `s ``%` `3` `=``=` `0``:``        ``removeAndPrintResult(arr, n, ``-``1``)``        ``return` `True`` ` ` ` ` ` `    ``# Find reminder``    ``remainder ``=` `s ``%` `3`` ` `    ``# If remainder is '1', we have to delete either``    ``# one element of remainder '1' or two elements``    ``# of remainder '2'``    ``if` `remainder ``=``=` `1``:``        ``rem_2 ``=` `[``0``]``*``2``        ``rem_2[``0``] ``=` `-``1``; rem_2[``1``] ``=` `-``1`` ` `        ``# Traverse array elements``        ``for` `i ``in` `range``(n):`` ` `            ``# Store first element of remainder '1'``            ``if` `arr[i] ``%` `3` `=``=` `1``:``                ``removeAndPrintResult(arr, n, i)``                ``return` `True`` ` `            ``if` `arr[i] ``%` `3` `=``=` `2``:`` ` `                ``# If this is first occurrence of remainder 2``                ``if` `rem_2[``0``] ``=``=` `-``1``:``                    ``rem_2[``0``] ``=` `i`` ` `                ``# If second occurrence``                ``elif` `rem_2[``1``] ``=``=` `-``1``:``                    ``rem_2[``1``] ``=` `i`` ` `        ``if` `rem_2[``0``] !``=` `-``1` `and` `rem_2[``1``] !``=` `-``1``:``            ``removeAndPrintResult(arr, n, rem_2[``0``], rem_2[``1``])``            ``return` `True`` ` `    ``# If remainder is '2', we have to delete either``    ``# one element of remainder '2' or two elements``    ``# of remainder '1'``    ``elif` `remainder ``=``=` `2``:``        ``rem_1 ``=` `[``0``]``*``2``        ``rem_1[``0``] ``=` `-``1``; rem_1[``1``] ``=` `-``1`` ` `        ``# traverse array elements``        ``for` `i ``in` `range``(n):`` ` `            ``# store first element of remainder '2'``            ``if` `arr[i] ``%` `3` `=``=` `2``:``                ``removeAndPrintResult(arr, n, i)``                ``return` `True`` ` `            ``if` `arr[i] ``%` `3` `=``=` `1``:`` ` `                ``# If this is first occurrence of remainder 1``                ``if` `rem_1[``0``] ``=``=` `-``1``:``                    ``rem_1[``0``] ``=` `i``                 ` `                ``# If second occurrence``                ``elif` `rem_1[``1``] ``=``=` `-``1``:``                    ``rem_1[``1``] ``=` `i``                     ` `        ``if` `rem_1[``0``] !``=` `-``1` `and` `rem_1[``1``] !``=` `-``1``:``            ``removeAndPrintResult(arr, n, rem_1[``0``], rem_1[``1``])``            ``return` `True`` ` `    ``print``(``"Not possible"``)``    ``return` `False`` ` ` ` `# Driver code``if` `__name__ ``=``=` `"__main__"``:`` ` `    ``arr ``=` `[``4``, ``4``, ``1``, ``1``, ``1``, ``3``]``    ``n ``=` `len``(arr)``    ``largest3Multiple(arr, n)`` ` `# This code is contributed by``# sanjeev2552`

## C#

 `// C# program to find the largest number``// that can be mode from elements of the``// array and is divisible by 3``using` `System;``     ` `class` `GFG ``{`` ` `    ``// Number of digits``    ``static` `int` `MAX_SIZE = 10;`` ` `    ``// function to sort array of digits using``    ``// counts``    ``static` `void` `sortArrayUsingCounts(``int` `[]arr, ``                                     ``int` `n)``    ``{``        ``// Store count of all elements``        ``int``[] count = ``new` `int``[MAX_SIZE];``        ``for` `(``int` `i = 0; i < n; i++) ``        ``{``            ``count[arr[i]]++;``        ``}`` ` `        ``// Store``        ``int` `index = 0;``        ``for` `(``int` `i = 0; i < MAX_SIZE; i++) ``        ``{``            ``while` `(count[i] > 0) ``            ``{``                ``arr[index++] = i;``                ``count[i]--;``            ``}``        ``}``    ``}`` ` `    ``// Remove elements from arr[]``    ``// at indexes ind1 and ind2``    ``static` `void` `removeAndPrintResult(``int` `[]arr, ``int` `n, ``                                     ``int` `ind1, ``int` `ind2)``    ``{``        ``for` `(``int` `i = n - 1; i >= 0; i--)``        ``{``            ``if` `(i != ind1 && i != ind2) ``            ``{``                ``Console.Write(arr[i]);``            ``}``        ``}``    ``}`` ` `    ``// Returns largest multiple of 3 ``    ``// that can be formed using``    ``// arr[] elements.``    ``static` `Boolean largest3Multiple(``int` `[]arr, ``                                    ``int` `n)``    ``{``        ``// Sum of all array element``        ``int` `sum = accumulate(arr, 0, n);`` ` `        ``// Sort array element in increasing order``        ``sortArrayUsingCounts(arr, n);`` ` `        ``// If sum is divisible by 3, ``        ``// no need to delete an element``        ``if` `(sum % 3 == 0) ``        ``{``            ``removeAndPrintResult(arr, n, -1, -1);``            ``return` `true``;``        ``}`` ` ` ` ` ` `        ``// Find reminder``        ``int` `remainder = sum % 3;`` ` `        ``// If remainder is '1', we have to ``        ``// delete either one element of ``        ``// remainder '1' or two elements of ``        ``// remainder '2'``        ``if` `(remainder == 1)``        ``{``            ``int``[] rem_2 = ``new` `int``;``            ``rem_2 = -1;``            ``rem_2 = -1;`` ` `            ``// Traverse array elements``            ``for` `(``int` `i = 0; i < n; i++) ``            ``{``                 ` `                ``// Store first element of remainder '1'``                ``if` `(arr[i] % 3 == 1)``                ``{``                    ``removeAndPrintResult(arr, n, i, -1);``                    ``return` `true``;``                ``}`` ` `                ``if` `(arr[i] % 3 == 2)``                ``{``                     ` `                    ``// If this is first occurrence``                    ``// of remainder 2``                    ``if` `(rem_2 == -1)``                    ``{``                        ``rem_2 = i;``                    ``}``                     ` `                    ``// If second occurrence``                    ``else` `if` `(rem_2 == -1) ``                    ``{``                        ``rem_2 = i;``                    ``}``                ``}``            ``}`` ` `            ``if` `(rem_2 != -1 && ``                ``rem_2 != -1) ``            ``{``                ``removeAndPrintResult(arr, n, rem_2, ``                                              ``rem_2);``                ``return` `true``;``            ``}``        ``} ``         ` `        ``// If remainder is '2', we have to ``        ``// delete either one element of ``        ``// remainder '2' or two elements of``        ``// remainder '1'``        ``else` `if` `(remainder == 2) ``        ``{``            ``int``[] rem_1 = ``new` `int``;``            ``rem_1 = -1;``            ``rem_1 = -1;`` ` `            ``// traverse array elements``            ``for` `(``int` `i = 0; i < n; i++) ``            ``{``                 ` `                ``// store first element of remainder '2'``                ``if` `(arr[i] % 3 == 2) ``                ``{``                    ``removeAndPrintResult(arr, n, i, -1);``                    ``return` `true``;``                ``}`` ` `                ``if` `(arr[i] % 3 == 1) ``                ``{``                     ` `                    ``// If this is first occurrence``                    ``// of remainder 1``                    ``if` `(rem_1 == -1) ``                    ``{``                        ``rem_1 = i;``                    ``} ``                     ` `                    ``// If second occurrence``                    ``else` `if` `(rem_1 == -1) ``                    ``{``                        ``rem_1 = i;``                    ``}``                ``}``            ``}`` ` `            ``if` `(rem_1 != -1 && ``                ``rem_1 != -1)``            ``{``                ``removeAndPrintResult(arr, n, rem_1, ``                                             ``rem_1);``                ``return` `true``;``            ``}``        ``}``        ``Console.Write(``"Not possible"``);``        ``return` `false``;``    ``}`` ` `    ``static` `int` `accumulate(``int``[] arr,``                          ``int` `start, ``                          ``int` `end) ``    ``{``        ``int` `sum = 0;``        ``for` `(``int` `i = 0; i < arr.Length; i++) ``        ``{``            ``sum += arr[i];``        ``}``        ``return` `sum;``    ``}``     ` `    ``// Driver code``    ``public` `static` `void` `Main(String[] args)``    ``{``        ``int` `[]arr = {4, 4, 1, 1, 1, 3};``        ``int` `n = arr.Length;``        ``largest3Multiple(arr, n);``    ``}``}`` ` `// This code is contributed by 29AjayKumar`

## Javascript

 ``

Output:

`4431`

Time Complexity : O(n)
This article is contributed by Nishant Singh. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.