Dada una array arr[] que consta de N enteros que son 0 o 7 , la tarea es encontrar el número más grande que se puede formar utilizando los elementos de la array de manera que sea divisible por 50 .
Ejemplos:
Entrada: arr[] = {7, 7, 7, 7, 7, 7, 0, 0, 0, 0, 0, 0, 0}
Salida: 777770000000Entrada: arr[] = {7, 0}
Salida: 0
Enfoque ingenuo: el enfoque más simple para resolver este problema se basa en las siguientes observaciones:
- Visualizando que 50 es igual a 5 * 10 , por lo tanto , cualquier cero final insertado se dividirá por 10 presente como un factor de 50 . Por lo tanto, la tarea se reduce a combinar 7 de manera que sean divisibles por 5 y para que un número sea divisible por 5 , su lugar de unidad debe ser 0 o 5 .
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es calcular la frecuencia de 7 s y 0 s presentes en la array y generar el número requerido que es divisible por 50 . Siga los pasos a continuación para resolver el problema:
- Cuente el número de 7 s y 0 s presentes en la array.
- Calcule el factor de 5 más cercano a la cuenta de 7 s presente en la array (ya que 35 es el factor 5 más pequeño que se puede obtener usando solo 7 s)
- Muestra el número calculado de 7 .
- Agregue ceros finales al número hecho arriba.
Casos de esquina a considerar:
- Si el conteo de 0 en el arreglo es 0 (entonces, la tarea es verificar si el conteo de 7 en el arreglo es divisible por 50 o no.
- Si el conteo de 7 es menor que 5 y no hay 0 en la array, simplemente imprima «No es posible».
- Si el conteo de 7s es menor que 5 y 0 está presente, simplemente imprima ‘0’.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Print the largest number divisible by 50
void printLargestDivisible(int arr[], int N)
{
int i, count0 = 0, count7 = 0;
for (i = 0; i < N; i++) {
// Counting number of 0s and 7s
if (arr[i] == 0)
count0++;
else
count7++;
}
// If count of 7 is divisible by 50
if (count7 % 50 == 0) {
while (count7--)
cout << 7;
while (count0--)
cout << 0;
}
// If count of 7 is less than 5
else if (count7 < 5) {
if (count0 == 0)
cout << "No";
else
cout << "0";
}
// If count of 7 is not
// divisible by 50
else {
// Count of groups of 5 in which
// count of 7s can be grouped
count7 = count7 - count7 % 5;
while (count7--)
cout << 7;
while (count0--)
cout << 0;
}
}
// Driver Code
int main()
{
// Given array
int arr[] = { 0, 7, 0, 7, 7, 7, 7, 0,
0, 0, 0, 0, 0, 7, 7, 7 };
// Size of the array
int N = sizeof(arr) / sizeof(arr[0]);
printLargestDivisible(arr, N);
return 0;
}
Java
// Java program of the above approach
import java.io.*;
class GFG {
// Print the largest number divisible by 50
static void printLargestDivisible(int arr[], int N)
{
int i, count0 = 0, count7 = 0;
for (i = 0; i < N; i++) {
// Counting number of 0s and 7s
if (arr[i] == 0)
count0++;
else
count7++;
}
// If count of 7 is divisible by 50
if (count7 % 50 == 0) {
while (count7 != 0)
{
System.out.print(7);
count7 -= 1;
}
while (count0 != 0)
{
System.out.print(0);
count0 -= 1;
}
}
// If count of 7 is less than 5
else if (count7 < 5) {
if (count0 == 0)
System.out.print("No");
else
System.out.print( "0");
}
// If count of 7 is not
// divisible by 50
else {
// Count of groups of 5 in which
// count of 7s can be grouped
count7 = count7 - count7 % 5;
while (count7 != 0)
{
System.out.print(7);
count7 -= 1;
}
while (count0 != 0)
{
System.out.print(0);
count0 -= 1;
}
}
}
// Driver Code
public static void main(String[] args)
{
// Given array
int arr[] = { 0, 7, 0, 7, 7, 7, 7, 0,
0, 0, 0, 0, 0, 7, 7, 7 };
// Size of the array
int N = arr.length;
printLargestDivisible(arr, N);
}
}
// This code is contributed by jana_sayantan.
Python3
# Python3 Program for the above approach
# Print the largest number divisible by 50
def printLargestDivisible(arr, N) :
count0 = 0; count7 = 0;
for i in range(N) :
# Counting number of 0s and 7s
if (arr[i] == 0) :
count0 += 1;
else :
count7 += 1;
# If count of 7 is divisible by 50
if (count7 % 50 == 0) :
while (count7) :
count7 -= 1;
print(7, end = "");
while (count0) :
count0 -= 1;
print(count0, end = "");
# If count of 7 is less than 5
elif (count7 < 5) :
if (count0 == 0) :
print("No", end = "");
else :
print("0", end = "");
# If count of 7 is not
# divisible by 50
else :
# Count of groups of 5 in which
# count of 7s can be grouped
count7 = count7 - count7 % 5;
while (count7) :
count7 -= 1;
print(7, end = "");
while (count0) :
count0 -= 1;
print(0, end = "");
# Driver Code
if __name__ == "__main__" :
# Given array
arr = [ 0, 7, 0, 7, 7, 7, 7, 0, 0, 0, 0, 0, 0, 7, 7, 7 ];
# Size of the array
N = len(arr);
printLargestDivisible(arr, N);
# This code is contributed by AnkThon
C#
// C# program of the above approach
using System;
public class GFG {
// Print the largest number divisible by 50
static void printLargestDivisible(int []arr, int N)
{
int i, count0 = 0, count7 = 0;
for (i = 0; i < N; i++)
{
// Counting number of 0s and 7s
if (arr[i] == 0)
count0++;
else
count7++;
}
// If count of 7 is divisible by 50
if (count7 % 50 == 0) {
while (count7 != 0)
{
Console.Write(7);
count7 -= 1;
}
while (count0 != 0)
{
Console.Write(0);
count0 -= 1;
}
}
// If count of 7 is less than 5
else if (count7 < 5) {
if (count0 == 0)
Console.Write("No");
else
Console.Write( "0");
}
// If count of 7 is not
// divisible by 50
else {
// Count of groups of 5 in which
// count of 7s can be grouped
count7 = count7 - count7 % 5;
while (count7 != 0)
{
Console.Write(7);
count7 -= 1;
}
while (count0 != 0)
{
Console.Write(0);
count0 -= 1;
}
}
}
// Driver Code
public static void Main(String[] args)
{
// Given array
int []arr = { 0, 7, 0, 7, 7, 7, 7, 0,
0, 0, 0, 0, 0, 7, 7, 7 };
// Size of the array
int N = arr.Length;
printLargestDivisible(arr, N);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript Program for the above approach
// Print the largest number divisible by 50
function printLargestDivisible(arr, N)
{
var i, count0 = 0, count7 = 0;
for (i = 0; i < N; i++) {
// Counting number of 0s and 7s
if (arr[i] == 0)
count0++;
else
count7++;
}
// If count of 7 is divisible by 50
if (count7 % 50 == 0) {
while (count7--)
document.write(7);
while (count0--)
document.write(0);
}
// If count of 7 is less than 5
else if (count7 < 5) {
if (count0 == 0)
document.write("No");
else
document.write("0");
}
// If count of 7 is not
// divisible by 50
else {
// Count of groups of 5 in which
// count of 7s can be grouped
count7 = count7 - count7 % 5;
while (count7--)
document.write(7);
while (count0--)
document.write(0);
}
}
// Driver Code
// Given array
var arr = [ 0, 7, 0, 7, 7, 7, 7, 0,
0, 0, 0, 0, 0, 7, 7, 7 ];
// Size of the array
var N = arr.length;
printLargestDivisible(arr, N);
</script>
Producción:
7777700000000
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por parthbanathia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA