El mayor número divisible por 90 que se puede hacer usando 0 y 5

Dada una array que contiene N elementos. Cada elemento es 0 o 5. Encuentre el número más grande divisible por 90 que se pueda formar usando cualquier número de elementos de esta array y organizándolos de cualquier manera.

Ejemplos :  

Input : arr[] = {5, 5, 5, 5, 5, 5, 5, 5, 0, 5, 5}
Output : 5555555550

Input : arr[] = {5, 0}
Output : 0 

Dado que podemos elegir y permutar cualquier cantidad de elementos, solo importa la cantidad de 0 y 5 en la array. Así que almacenemos el conteo como c0 y c5 respectivamente. 
El número tiene que hacerse un múltiplo de 90 que es 9*10. Por lo tanto, el número tiene que ser un múltiplo de 9 y 10. 
Las reglas de divisibilidad son las siguientes:  

• Para que un número sea divisible por 10, debe terminar en 0.
• Para que un número sea divisible por 9, la suma de los dígitos debe ser divisible por 9. Dado que el único dígito distinto de cero que se permite usar es 5, el número de veces que usamos 5 tiene que ser un múltiplo de 9, de modo que el suma será un múltiplo de 45, es decir, divisible por 9.

Hay 3 posibilidades:  

• c0=0 . Esto implica que ningún número puede hacerse divisible por 10.
• c5=0. Esto implica que el único número que puede hacerse divisible por 90 es 0.
• Si las dos condiciones anteriores son falsas. Agrupemos el número de 5 en grupos de 9. Habrá grupos de suelo (c5/9) que estén completamente llenos, podemos usar todos los 5 de todos los grupos para obtener el número de 5 como múltiplo de 9, lo cual también hace que el dígito sume un múltiplo de 9. Como aumentar el número de ceros no afecta la divisibilidad, podemos usar todos los ceros.

A continuación se muestra la implementación del enfoque anterior: 
 

// CPP program to find largest number
// divisible by 90 that can be made
// using 0 and 5
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find largest number
// divisible by 90 that can be made
// using 0 and 5
void printLargestDivisible(int n, int a[])
{
    // Count of 0s and 5s
    int i, c0 = 0, c5 = 0;
    for (i = 0; i < n; i++) {
        if (a[i] == 0)
            c0++;
        else
            c5++;
    }
 
    // The number of 5s that can be used
    c5 = floor(c5 / 9) * 9;
    if (c0 == 0) // The number can't be
        cout << -1; // made multiple of 10
    else if (c5 == 0) // The only multiple of 90
        cout << 0; // that can be made is 0
    else {
        for (i = 0; i < c5; i++)
            cout << 5;
        for (i = 0; i < c0; i++)
            cout << 0;
    }
}
 
// Driver Code
int main()
{
    int a[] = { 5, 5, 5, 5, 5, 5, 5, 5, 0, 5, 5 };
 
    int n = sizeof(a) / sizeof(a[0]);
 
    printLargestDivisible(n, a);
 
    return 0;
}

// Java program to find largest number
// divisible by 90 that can be made
// using 0 and 5
 
import java.io.*;
 
class GFG {
 
// Function to find largest number
// divisible by 90 that can be made
// using 0 and 5
static void printLargestDivisible(int n, int a[])
{
    // Count of 0s and 5s
    int i, c0 = 0, c5 = 0;
    for (i = 0; i < n; i++) {
        if (a[i] == 0)
            c0++;
        else
            c5++;
    }
 
    // The number of 5s that can be used
    c5 = (int)Math.floor(c5 / 9) * 9;
    if (c0 == 0) // The number can't be
        System.out.print(-1); // made multiple of 10
    else if (c5 == 0) // The only multiple of 90
        System.out.println(0); // that can be made is 0
    else {
        for (i = 0; i < c5; i++)
            System.out.print(5);
        for (i = 0; i < c0; i++)
            System.out.print(0);
    }
}
 
// Driver Code
 
    public static void main (String[] args) {
        int a[] = { 5, 5, 5, 5, 5, 5, 5, 5, 0, 5, 5 };
 
    int n = a.length;
 
    printLargestDivisible(n, a);
    }
}
// This code is contributed
// by shs

# Python3 program to find largest number
# divisible by 90 that can be made
# using 0 and 5
 
# from math import every methods
from math import *
 
# Function to find largest number
# divisible by 90 that can be made
# using 0 and 5
def printLargestDivisible(n, a) :
 
    # Count of 0s and 5s
    c0, c5 = 0, 0
 
    for i in range(n) :
 
        if a[i] == 0 :
            c0 += 1
        else :
            c5 += 1
 
    # The number of 5s that can be used
    c5 = floor(c5 / 9) * 9
 
    if c0 == 0 : # The number can't be
        print(-1,end = "") # made multiple of 10
 
    elif c5 == 0 : # The only multiple of 90
        print(0,end = "") # that can be made is 0
 
    else :
 
        for i in range(c5) :
            print(5,end = "")
        for i in range(c0) :
            print(0, end = "")
 
 
 
# Driver code
if __name__ == "__main__" :
 
    a = [ 5, 5, 5, 5, 5, 5, 5, 5, 0, 5, 5]
    n = len(a)
 
    # Function calling
    printLargestDivisible(n, a)
 
# This code is contributed by
# ANKITRAI1

// C# program to find largest number
// divisible by 90 that can be made
// using 0 and 5
using System;
 
class GFG {
 
// Function to find largest number
// divisible by 90 that can be made
// using 0 and 5
public static void printLargestDivisible(int n,
                                       int[] a)
{
     
    // Count of 0s and 5s
    int i, c0 = 0, c5 = 0;
    for (i = 0; i < n; i++)
    {
        if (a[i] == 0)
        {
            c0++;
        }
        else
        {
            c5++;
        }
    }
     
    // The number of 5s that can be used
    c5 = (c5 / 9) * 9;
     
    // The number can't be
    if (c0 == 0)
    {
         
        // made multiple of 10
        Console.Write(-1);
    }
     
    // The only multiple of 90
    else if (c5 == 0)
    {
         
        // that can be made is 0
        Console.WriteLine(0);
    }
    else
    {
        for (i = 0; i < c5; i++)
        {
            Console.Write(5);
        }
        for (i = 0; i < c0; i++)
        {
            Console.Write(0);
        }
    }
}
 
    // Driver Code
    public static void Main(string[] args)
    {
        int[] a = new int[] {5, 5, 5, 5, 5,
                         5, 5, 5, 0, 5, 5};
        int n = a.Length;
        printLargestDivisible(n, a);
    }
}
 
// This code is contributed by Shrikant13

<?php
// PHP program to find largest number
// divisible by 90 that can be made
// using 0 and 5
 
// Function to find largest number
// divisible by 90 that can be made
// using 0 and 5
function printLargestDivisible($n, $a)
{
    // Count of 0s and 5s
    $i;
    $c0 = 0;
    $c5 = 0;
    for ($i = 0; $i < $n; $i++)
    {
        if ($a[$i] == 0)
            $c0++;
        else
            $c5++;
    }
 
    // The number of 5s that can be used
    $c5 = floor($c5 / 9) * 9;
    if ($c0 == 0) // The number can't be
        echo -1;  // made multiple of 10
    else if ($c5 == 0) // The only multiple of 90
        echo 0;        // that can be made is 0
    else
    {
        for ($i = 0; $i < $c5; $i++)
            echo 5;
        for ($i = 0; $i < $c0; $i++)
            echo 0;
    }
}
 
// Driver Code
$a = array( 5, 5, 5, 5, 5, 5,
            5, 5, 0, 5, 5 );
 
$n = sizeof($a);
 
printLargestDivisible($n, $a);
 
// This code is contributed by ajit
?>

<script>
    // Javascript program to find largest number
    // divisible by 90 that can be made
    // using 0 and 5
     
    // Function to find largest number
    // divisible by 90 that can be made
    // using 0 and 5
    function printLargestDivisible(n, a)
    {
 
        // Count of 0s and 5s
        let i, c0 = 0, c5 = 0;
        for (i = 0; i < n; i++)
        {
            if (a[i] == 0)
            {
                c0++;
            }
            else
            {
                c5++;
            }
        }
 
        // The number of 5s that can be used
        c5 = parseInt(c5 / 9, 10) * 9;
 
        // The number can't be
        if (c0 == 0)
        {
 
            // made multiple of 10
            document.write(-1);
        }
 
        // The only multiple of 90
        else if (c5 == 0)
        {
 
            // that can be made is 0
            document.write(0 + "</br>");
        }
        else
        {
            for (i = 0; i < c5; i++)
            {
                document.write(5);
            }
            for (i = 0; i < c0; i++)
            {
                document.write(0);
            }
        }
    }
     
    let a = [5, 5, 5, 5, 5, 5, 5, 5, 0, 5, 5];
    let n = a.length;
    printLargestDivisible(n, a);
     
</script>

5555555550

Complejidad temporal: O(N), donde N es el número de elementos del arreglo.