Encuentre el mayor múltiplo de 3 de la array de dígitos | Conjunto 2 (En tiempo O(n) y espacio O(1))

Dada una array de dígitos (contiene elementos del 0 al 9). Encuentre el número más grande que se puede formar a partir de algunos o todos los dígitos de la array y es divisible por 3. El mismo elemento puede aparecer varias veces en la array, pero cada elemento de la array solo se puede usar una vez. 
Ejemplos: 
 

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

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

Preguntado en: entrevista de Google
 

Hemos discutido una solución basada en colas . Ambas soluciones (discutidas en publicaciones anteriores y esta) se basan en el hecho de que un número es divisible por 3 si y solo si la suma de los dígitos del número es divisible por 3. 
Por ejemplo, consideremos 555, es divisible por 3 porque la suma de dígitos es 5 + 5 + 5 = 15, que es divisible por 3. Si una suma de dígitos no es divisible por 3, entonces el resto debe ser 1 o 2. 
Si obtenemos el resto, ‘1’ o ‘2 ‘, tenemos que quitar máximo dos dígitos para hacer un número que sea divisible por 3: 
 

  1. Si el resto es ‘1’: Tenemos que quitar un solo dígito que tenga resto ‘1’ o dos dígitos que tengan resto ‘2’ ( 2 + 2 => 4 % 3 => ‘1’)
  2. Si el resto es ‘2’: Tenemos que quitar un solo dígito que tenga resto ‘2’ o dos dígitos que tengan resto ‘1’ (1 + 1 => 2 % 3 => 2).

Ejemplos: 
 

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 

A continuación se muestra la implementación de la idea anterior.
 

C++

// C++ program to find the largest number
// that can be mode from elements of the
// array and is divisible by 3
#include<bits/stdc++.h>
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[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);
                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[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);
                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;
        }
    }
  
    cout << "Not possible";
    return false;
}
  
// Driver code
int main()
{
    int arr[] = {4, 4, 1, 1, 1, 3 } ;
    int n = sizeof(arr)/sizeof(arr[0]);
    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[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;
            }
        }
        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

<script>
// JavaScript program to find the largest number
// that can be mode from elements of the
// array and is divisible by 3
  
// Number of digits
const MAX_SIZE = 10;
  
// function to sort array of digits using
// counts
function sortArrayUsingCounts(arr, n)
{
    // Store count of all elements
    let count = new Uint8Array(MAX_SIZE);
    for (let i = 0; i < n; i++)
        count[arr[i]]++;
  
    // Store
    let index = 0;
    for (let i = 0; i < MAX_SIZE; i++)
        while (count[i] > 0)
            arr[index++] = i, count[i]--;
}
  
// Remove elements from arr[] at indexes ind1 and ind2
function removeAndPrintResult(arr, n, ind1, ind2 = -1)
{
    for (let i = n-1; i >=0; i--)
        if (i != ind1 && i != ind2)
            document.write(arr[i]) ;
}
  
// Returns largest multiple of 3 that can be formed
// using arr[] elements.
function largest3Multiple(arr, n)
{
    // Sum of all array element
    let sum = arr.reduce((a, b) => a + b, 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);
        return true ;
    }
  
  
  
    // Find reminder
    let 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)
    {
        let rem_2 = new Array(2);
        rem_2[0] = -1, rem_2[1] = -1;
  
        // Traverse array elements
        for (let 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[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)
    {
        let rem_1 = new Array(2);
        rem_1[0] = -1, rem_1[1] = -1;
  
        // traverse array elements
        for (let 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[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;
        }
    }
  
    document.write("Not possible");
    return false;
}
  
// Driver code
    let arr = [4 , 4 , 1 , 1 , 1 , 3];
    let n = arr.length;
    largest3Multiple(arr, n);
  
  
  
// This code is contributed by Surbhi Tyagi.
</script>

Producción: 
 

4431

Complejidad del tiempo: O(n) 
Este artículo es una contribución de Nishant Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *