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:
- 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’)
- 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