Dada una array de enteros no negativos. Encuentre el mayor múltiplo de 3 que se puede formar a partir de elementos de array.
Por ejemplo, si la array de entrada es {8, 1, 9}, la salida debería ser «9 8 1», y si la array de entrada es {8, 1, 7, 6, 0}, la salida debería ser «8 7 6 0”.
Método 1 (Fuerza bruta) :
El enfoque simple y directo es generar todas las combinaciones de los elementos y realizar un seguimiento del número más grande formado que es divisible por 3.
Complejidad del tiempo: O (nx 2^n). Habrá 2^n combinaciones de elementos de array. Comparar cada combinación con el número más grande hasta el momento puede llevar O(n) tiempo.
Espacio auxiliar: O(n) // para evitar el desbordamiento de enteros, se supone que el número más grande se almacena en forma de array.
Método 2 (complicado) :
Este problema se puede resolver de manera eficiente con la ayuda de O(n) espacio extra. Este método se basa en los siguientes datos sobre números que son múltiplos de 3.
- Un número es múltiplo de 3 si y solo si la suma de los dígitos del número es múltiplo de 3. Por ejemplo, consideremos 8760, es un múltiplo de 3 porque la suma de los dígitos es 8 + 7+ 6+ 0 = 21, que es múltiplo de 3.
- Si un número es múltiplo de 3, entonces todas sus permutaciones también son múltiplos de 3. Por ejemplo, dado que 6078 es un múltiplo de 3, los números 8760, 7608, 7068, … también son múltiplos de 3.
- Obtenemos el mismo resto cuando dividimos el número y la suma de los dígitos del número. Por ejemplo, si dividimos el número 151 y sumamos los dígitos 7 entre 3, obtenemos el mismo resto 1.
¿Cuál es la idea detrás de los hechos anteriores?
El valor de 10%3 y 100%3 es 1. Lo mismo es cierto para todas las potencias superiores de 10, porque 3 divide a 9, 99, 999, … etc.
Consideremos un número n de 3 dígitos para probar los hechos anteriores. Sean los dígitos primero, segundo y tercero de n ‘a’, ‘b’ y ‘c’ respectivamente. n se puede escribir como
n = 100.a + 10.b + c
Dado que (10^x)%3 es 1 para cualquier x, la expresión anterior da el mismo resto que la siguiente expresión
1.a + 1.b + c
Entonces, el resto obtenido por la suma de dígitos y ‘n’ es el mismo.
La siguiente es una solución basada en la observación anterior.
- Ordene la array en orden no decreciente.
- Tome tres colas. Uno para almacenar elementos que al dividir por 3 da como resultado 0. La segunda cola almacena dígitos que al dividir por 3 da como resto 1. La tercera cola almacena dígitos que al dividir por 3 da como resto 2. Llámalos como cola0, cola1 y cola2
- Encuentra la suma de todos los dígitos.
- Se presentan tres casos:
- …… 4.1 La suma de los dígitos es divisible por 3. Retire todos los dígitos de las tres colas. Ordenarlos en orden no creciente. Salida de la array.
- …… 4.2 La suma de los dígitos produce el resto 1 cuando se divide por 3.
Retire un elemento de la cola1. Si la cola1 está vacía, elimine dos elementos de la cola2. Si queue2 contiene menos de dos elementos, el número no es posible.- …… 4.3 La suma de dígitos produce el resto 2 cuando se divide por 3.
Quite un elemento de la cola2. Si la cola2 está vacía, elimine dos elementos de la cola1. Si cola1 contiene menos de dos elementos, el número no es posible.- Finalmente, vacíe todas las colas en una array auxiliar. Ordene la array auxiliar en orden no creciente. Salida de la array auxiliar.
El siguiente código funciona solo si las arrays de entrada tienen números del 0 al 9. Se puede ampliar fácilmente para cualquier array de enteros positivos. Solo tenemos que modificar la parte donde ordenamos la array en orden decreciente, al final del código.
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// This function puts all elements of 3 queues in the auxiliary array
void populateAux(int aux[], queue<int> queue0, queue<int> queue1,
queue<int> queue2, int* top)
{
// Put all items of first queue in aux[]
while (!queue0.empty()) {
aux[(*top)++] = queue0.front();
queue0.pop();
}
// Put all items of second queue in aux[]
while (!queue1.empty()) {
aux[(*top)++] = queue1.front();
queue1.pop();
}
// Put all items of third queue in aux[]
while (!queue2.empty()) {
aux[(*top)++] = queue2.front();
queue2.pop();
}
}
// The main function that finds the largest possible multiple of
// 3 that can be formed by arr[] elements
int findMaxMultupleOf3(int arr[], int size)
{
// Step 1: sort the array in non-decreasing order
sort(arr, arr + size);
// Create 3 queues to store numbers with remainder 0, 1
// and 2 respectively
queue<int> queue0, queue1, queue2;
// Step 2 and 3 get the sum of numbers and place them in
// corresponding queues
int i, sum;
for (i = 0, sum = 0; i < size; ++i) {
sum += arr[i];
if ((arr[i] % 3) == 0)
queue0.push(arr[i]);
else if ((arr[i] % 3) == 1)
queue1.push(arr[i]);
else
queue2.push(arr[i]);
}
// Step 4.2: The sum produces remainder 1
if ((sum % 3) == 1) {
// either remove one item from queue1
if (!queue1.empty())
queue1.pop();
// or remove two items from queue2
else {
if (!queue2.empty())
queue2.pop();
else
return 0;
if (!queue2.empty())
queue2.pop();
else
return 0;
}
}
// Step 4.3: The sum produces remainder 2
else if ((sum % 3) == 2) {
// either remove one item from queue2
if (!queue2.empty())
queue2.pop();
// or remove two items from queue1
else {
if (!queue1.empty())
queue1.pop();
else
return 0;
if (!queue1.empty())
queue1.pop();
else
return 0;
}
}
int aux[size], top = 0;
// Empty all the queues into an auxiliary array.
populateAux(aux, queue0, queue1, queue2, &top);
// sort the array in non-increasing order
sort(aux, aux + top, greater<int>());
// print the result
for (int i = 0; i < top; ++i)
cout << aux[i] << " ";
return top;
}
int main()
{
int arr[] = { 8, 1, 7, 6, 0 };
int size = sizeof(arr) / sizeof(arr[0]);
if (findMaxMultupleOf3(arr, size) == 0)
cout << "Not Possible";
return 0;
}
C
/* A program to find the largest multiple of 3 from an array of elements */
#include <stdio.h>
#include <stdlib.h>
// A queue node
typedef struct Queue {
int front;
int rear;
int capacity;
int* array;
} Queue;
// A utility function to create a queue with given capacity
Queue* createQueue(int capacity)
{
Queue* queue = (Queue*)malloc(sizeof(Queue));
queue->capacity = capacity;
queue->front = queue->rear = -1;
queue->array = (int*)malloc(queue->capacity * sizeof(int));
return queue;
}
// A utility function to check if queue is empty
int isEmpty(Queue* queue)
{
return queue->front == -1;
}
// A function to add an item to queue
void Enqueue(Queue* queue, int item)
{
queue->array[++queue->rear] = item;
if (isEmpty(queue))
++queue->front;
}
// A function to remove an item from queue
int Dequeue(Queue* queue)
{
int item = queue->array[queue->front];
if (queue->front == queue->rear)
queue->front = queue->rear = -1;
else
queue->front++;
return item;
}
// A utility function to print array contents
void printArr(int* arr, int size)
{
int i;
for (i = 0; i < size; ++i)
printf("%d ", arr[i]);
}
/* Following two functions are needed for library function qsort().
Refer following link for help of qsort()
http:// www.cplusplus.com/reference/clibrary/cstdlib/qsort/ */
int compareAsc(const void* a, const void* b)
{
return *(int*)a > *(int*)b;
}
int compareDesc(const void* a, const void* b)
{
return *(int*)a < *(int*)b;
}
// This function puts all elements of 3 queues in the auxiliary array
void populateAux(int* aux, Queue* queue0, Queue* queue1,
Queue* queue2, int* top)
{
// Put all items of first queue in aux[]
while (!isEmpty(queue0))
aux[(*top)++] = Dequeue(queue0);
// Put all items of second queue in aux[]
while (!isEmpty(queue1))
aux[(*top)++] = Dequeue(queue1);
// Put all items of third queue in aux[]
while (!isEmpty(queue2))
aux[(*top)++] = Dequeue(queue2);
}
// The main function that finds the largest possible multiple of
// 3 that can be formed by arr[] elements
int findMaxMultupleOf3(int* arr, int size)
{
// Step 1: sort the array in non-decreasing order
qsort(arr, size, sizeof(int), compareAsc);
// Create 3 queues to store numbers with remainder 0, 1
// and 2 respectively
Queue* queue0 = createQueue(size);
Queue* queue1 = createQueue(size);
Queue* queue2 = createQueue(size);
// Step 2 and 3 get the sum of numbers and place them in
// corresponding queues
int i, sum;
for (i = 0, sum = 0; i < size; ++i) {
sum += arr[i];
if ((arr[i] % 3) == 0)
Enqueue(queue0, arr[i]);
else if ((arr[i] % 3) == 1)
Enqueue(queue1, arr[i]);
else
Enqueue(queue2, arr[i]);
}
// Step 4.2: The sum produces remainder 1
if ((sum % 3) == 1) {
// either remove one item from queue1
if (!isEmpty(queue1))
Dequeue(queue1);
// or remove two items from queue2
else {
if (!isEmpty(queue2))
Dequeue(queue2);
else
return 0;
if (!isEmpty(queue2))
Dequeue(queue2);
else
return 0;
}
}
// Step 4.3: The sum produces remainder 2
else if ((sum % 3) == 2) {
// either remove one item from queue2
if (!isEmpty(queue2))
Dequeue(queue2);
// or remove two items from queue1
else {
if (!isEmpty(queue1))
Dequeue(queue1);
else
return 0;
if (!isEmpty(queue1))
Dequeue(queue1);
else
return 0;
}
}
int aux[size], top = 0;
// Empty all the queues into an auxiliary array.
populateAux(aux, queue0, queue1, queue2, &top);
// sort the array in non-increasing order
qsort(aux, top, sizeof(int), compareDesc);
// print the result
printArr(aux, top);
return top;
}
// Driver program to test above functions
int main()
{
int arr[] = { 8, 1, 7, 6, 0 };
int size = sizeof(arr) / sizeof(arr[0]);
if (findMaxMultupleOf3(arr, size) == 0)
printf("Not Possible");
return 0;
}
Java
/* Java program to find the largest multiple
of 3 that can be formed from an array
of elements */
import java.util.Arrays;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Collections;
public class Geeks {
// This function puts all elements of 3 queues in the
// array auxiliary
public static int populateAux(int aux[], Queue<Integer> queue0,
Queue<Integer> queue1, Queue<Integer> queue2)
{
int top=0;
// Put all items of first queue in aux[]
while(!queue0.isEmpty())
{
aux[top++]=queue0.remove();
}
// Put all items of second queue in aux[]
while(!queue1.isEmpty())
{
aux[top++]=queue1.remove();
}
// Put all items of third queue in aux[]
while(!queue2.isEmpty())
{
aux[top++]=queue2.remove();
}
//Return number of integer added to aux[]
return top;
}
// The main function that finds the largest possible multiple of
// 3 that can be formed by arr[] elements
public static boolean findMaxMultupleOf3(int arr[])
{
// Step 1: sort the array in non-decreasing order
Arrays.sort(arr);
// Create 3 queues to store numbers with remainder 0, 1
// and 2 respectively
Queue<Integer> queue0=new LinkedList<>();
Queue<Integer> queue1=new LinkedList<>();
Queue<Integer> queue2=new LinkedList<>();
// Step 2 and 3 get the sum of numbers and place them in
// corresponding queues
int sum=0;
for (int i = 0; i < arr.length; ++i)
{
sum += arr[i];
if ((arr[i] % 3) == 0)
queue0.add(arr[i]);
else if ((arr[i] % 3) == 1)
queue1.add(arr[i]);
else
queue2.add(arr[i]);
}
// Step 4.2: The sum produces remainder 1
if ((sum % 3) == 1)
{
// either remove one item from queue1
if (!queue1.isEmpty())
queue1.remove();
// or remove two items from queue2
else
{
if (!queue2.isEmpty())
queue2.remove();
else
return false;
if (!queue2.isEmpty())
queue2.remove();
else
return false;
}
}
// Step 4.3: The sum produces remainder 2
else if ((sum % 3) == 2)
{
// either remove one item from queue2
if (!queue2.isEmpty())
queue2.remove();
// or remove two items from queue1
else
{
if (!queue1.isEmpty())
queue1.remove();
else
return false;
if (!queue1.isEmpty())
queue1.remove();
else
return false;
}
}
int aux[]=new int[arr.length];
// Empty all the queues into an auxiliary array
// and get the number of integers added to aux[]
int top=populateAux(aux,queue0,queue1,queue2);
// sort the array in non-increasing order
Arrays.sort(aux,0,top);
// print the result
for (int i = top-1; i>=0; i--)
System.out.print(aux[i]+" ") ;
return true;
}
public static void main(String args[])
{
int arr[] = { 8, 1, 7, 6, 0 };
if (!findMaxMultupleOf3(arr))
System.out.println("Not possible") ;
}
}
// This code is contributed by Gaurav Tiwari
Python3
# Python3 program to find the largest multiple
# of 3 that can be formed from an array
# of elements
aux = []
# This function puts all elements of 3 queues in the
# array auxiliary
def populateAux(queue0, queue1, queue2):
global aux
top = 0
# Put all items of first queue in aux[]
while(len(queue0) > 0):
aux[top] = queue0.pop(0)
top += 1
# Put all items of second queue in aux[]
while(len(queue1) != 0):
aux[top] = queue1.pop(0)
top += 1
# Put all items of third queue in aux[]
while(len(queue2) != 0):
aux[top] = queue2.pop(0)
top += 1
# Return number of integer added to aux[]
return top
# The main function that finds the largest possible multiple of
# 3 that can be formed by arr[] elements
def findMaxMultupleOf3(arr):
global aux
# Step 1: sort the array in non-decreasing order
arr.sort()
# Create 3 queues to store numbers with remainder 0, 1
# and 2 respectively
queue0 = []
queue1 = []
queue2 = []
# Step 2 and 3 get the sum of numbers and place them in
# corresponding queues
sum = 0
for i in range(len(arr)):
sum += arr[i]
if ((arr[i] % 3) == 0):
queue0.append(arr[i])
elif ((arr[i] % 3) == 1):
queue1.append(arr[i])
else:
queue2.append(arr[i])
# Step 4.2: The sum produces remainder 1
if ((sum % 3) == 1):
# either remove one item from queue1
if (len(queue1) != 0):
queue1.pop(0)
# or remove two items from queue2
else:
if (len(queue2) != 0):
queue2.pop(0)
else:
return False
if (len(queue2) != 0):
queue2.pop(0)
else:
return False
# Step 4.3: The sum produces remainder 2
elif ((sum % 3) == 2):
# either remove one item from queue2
if (len(queue2) != 0):
queue2.pop(0)
# or remove two items from queue1
else:
if (len(queue1) != 0):
queue1.pop(0)
else:
return False
if (len(queue1) != 0):
queue1.pop(0)
else:
return False
aux = [0 for i in range(len(arr))]
# Empty all the queues into an auxiliary array
# and get the number of integers added to aux[]
top = populateAux(queue0, queue1, queue2)
# sort the array in non-increasing order
aux.sort(reverse=True)
# print the result
for i in range(0, top):
print(aux[i], end=" ")
return True
# Driver code
arr = [8, 1, 7, 6, 0]
if (not findMaxMultupleOf3(arr)):
print("Not possible")
# This code is contributed by phasing17
C#
/* C# program to find the largest multiple
of 3 that can be formed from an array
of elements */
using System;
using System.Collections.Generic;
class Geeks
{
// This function puts all elements of 3 queues in the
// array auxiliary
public static int populateAux(int []aux, Queue<int> queue0,
Queue<int> queue1, Queue<int> queue2)
{
int top = 0;
// Put all items of first queue in aux[]
while(queue0.Count != 0)
{
aux[top++] = queue0.Dequeue();
}
// Put all items of second queue in aux[]
while(queue1.Count != 0)
{
aux[top++] = queue1.Dequeue();
}
// Put all items of third queue in aux[]
while(queue2.Count != 0)
{
aux[top++] = queue2.Dequeue();
}
//Return number of integer added to aux[]
return top;
}
// The main function that finds the largest possible multiple of
// 3 that can be formed by arr[] elements
public static bool findMaxMultupleOf3(int []arr)
{
// Step 1: sort the array in non-decreasing order
Array.Sort(arr);
// Create 3 queues to store numbers with remainder 0, 1
// and 2 respectively
Queue<int> queue0 = new Queue<int>();
Queue<int> queue1 = new Queue<int>();
Queue<int> queue2 = new Queue<int>();
// Step 2 and 3 get the sum of numbers and place them in
// corresponding queues
int sum=0;
for (int i = 0; i < arr.Length; ++i)
{
sum += arr[i];
if ((arr[i] % 3) == 0)
queue0.Enqueue(arr[i]);
else if ((arr[i] % 3) == 1)
queue1.Enqueue(arr[i]);
else
queue2.Enqueue(arr[i]);
}
// Step 4.2: The sum produces remainder 1
if ((sum % 3) == 1)
{
// either remove one item from queue1
if (queue1.Count != 0)
queue1.Dequeue();
// or remove two items from queue2
else
{
if (queue2.Count != 0)
queue2.Dequeue();
else
return false;
if (queue2.Count != 0)
queue2.Dequeue();
else
return false;
}
}
// Step 4.3: The sum produces remainder 2
else if ((sum % 3) == 2)
{
// either remove one item from queue2
if (queue2.Count != 0)
queue2.Dequeue();
// or remove two items from queue1
else
{
if (queue1.Count != 0)
queue1.Dequeue();
else
return false;
if (queue1.Count != 0)
queue1.Dequeue();
else
return false;
}
}
int []aux = new int[arr.Length];
// Empty all the queues into an auxiliary array
// and get the number of integers added to aux[]
int top = populateAux(aux,queue0,queue1,queue2);
// sort the array in non-increasing order
Array.Sort(aux,0,top);
// print the result
for (int i = top-1; i >= 0; i--)
Console.Write(aux[i]+" ") ;
return true;
}
// Driver code
public static void Main()
{
int []arr = { 8, 1, 7, 6, 0 };
if (!findMaxMultupleOf3(arr))
Console.WriteLine("Not possible") ;
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
/* Javascript program to find the largest multiple
of 3 that can be formed from an array
of elements */
// This function puts all elements of 3 queues in the
// array auxiliary
function populateAux(aux, queue0, queue1, queue2)
{
let top = 0;
// Put all items of first queue in aux[]
while(queue0.length != 0)
{
aux[top++] = queue0.shift();
}
// Put all items of second queue in aux[]
while(queue1.length != 0)
{
aux[top++] = queue1.shift();
}
// Put all items of third queue in aux[]
while(queue2.length != 0)
{
aux[top++] = queue2.shift();
}
//Return number of integer added to aux[]
return top;
}
// The main function that finds the largest possible multiple of
// 3 that can be formed by arr[] elements
function findMaxMultupleOf3(arr)
{
// Step 1: sort the array in non-decreasing order
arr.sort(function(a, b){return a - b;});
// Create 3 queues to store numbers with remainder 0, 1
// and 2 respectively
let queue0 = [];
let queue1 = [];
let queue2 = [];
// Step 2 and 3 get the sum of numbers and place them in
// corresponding queues
let sum = 0;
for (let i = 0; i < arr.length; ++i)
{
sum += arr[i];
if ((arr[i] % 3) == 0)
queue0.push(arr[i]);
else if ((arr[i] % 3) == 1)
queue1.push(arr[i]);
else
queue2.push(arr[i]);
}
// Step 4.2: The sum produces remainder 1
if ((sum % 3) == 1)
{
// either remove one item from queue1
if (queue1.length != 0)
queue1.shift();
// or remove two items from queue2
else
{
if (queue2.length != 0)
queue2.shift();
else
return false;
if (queue2.length != 0)
queue2.shift();
else
return false;
}
}
// Step 4.3: The sum produces remainder 2
else if ((sum % 3) == 2)
{
// either remove one item from queue2
if (queue2.length != 0)
queue2.shift();
// or remove two items from queue1
else
{
if (queue1.length != 0)
queue1.shift();
else
return false;
if (queue1.length != 0)
queue1.shift();
else
return false;
}
}
let aux=new Array(arr.length);
// Empty all the queues into an auxiliary array
// and get the number of integers added to aux[]
let top=populateAux(aux, queue0, queue1, queue2);
// sort the array in non-increasing order
aux.sort(function(a, b){return a - b;});
// print the result
for (let i = top - 1; i >= 0; i--)
document.write(aux[i]+" ") ;
return true;
}
// Driver code
let arr = [ 8, 1, 7, 6, 0 ];
if (!findMaxMultupleOf3(arr))
document.write("Not possible") ;
// This code is contributed by rag2127.
</script>
Producción:
8 7 6 0
El método anterior se puede optimizar de las siguientes maneras.
- Podemos usar Heap Sort o Merge Sort para hacer que la complejidad del tiempo sea O (nLogn).
- Podemos evitar espacio adicional para las colas. Sabemos que se eliminarán como máximo dos elementos de la array de entrada. Entonces podemos realizar un seguimiento de dos elementos en dos variables.
- Al final, en lugar de ordenar la array nuevamente en orden descendente, podemos imprimir la array ordenada ascendente en orden inverso. Mientras imprimimos en orden inverso, podemos omitir los dos elementos que se eliminarán.
Complejidad de tiempo: O(nLogn), suponiendo que se utilice un algoritmo O(nLogn) para la clasificación.
Encuentra el mayor múltiplo de 3 | Conjunto 2 (En tiempo O(n) y espacio O(1))
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