Retos - 012: La abuela binaria

Nivel de dificultad aproximado (1 a 5): 3  

Enunciado del problema

Yuki es una chica con suerte. Su abuela Chika es una encantadora anciona, propietaria de una granja de ovejas, experta repostera y ninja de la costura, y tiene un avellanero detrás de casa. Yuki pide avellanas continuamente, pero su sabia abuela no permite que Yuki coma demasiadas para que no caiga enferma.

Chika es aficionada a los números binarios, así que propuso este juego a Yuki: ella diría un número N y Yuki escogería dos números, x e y, tales que x + y = N. Entonces, Chika daría a Yuki tantas avellanas como la cantidad de unos que tengan x e y en base 2. Por ejemplo, si Chika propone 7 y Yuki escoge 3 y 4, recibiría 2 (porque 3 en base 2 es 11) y 1 (porque 4 en base 2 es 100): 3 avellanas.

Yuki quiere saber la máxima cantidad de avellanas que podría obtener de Chika.

Entrada: La primera línea es el número de casos, y a continuación, cada caso en una nueva línea (un número entero, entre 0 y 10^19, que puede no caber en un entero de 32 bits).

Salida: Para cada caso, una línea conteniendo "Caso #x: M", donde x es el número de caso (desde 1) y M es el número máximo de avellanas.

(Asegúrate de que has leído las preguntas frecuentes antes de plantear tu solución)

Entradas y salidas de ejemplo 
Ejemplo de entrada:

3 

1 

6 

2135



Salida correspondiente:

Caso #1: 1 

Caso #2: 4 

Caso #3: 14
Procedencia del reto

Original en: Pregunta 2 del concurso Tuenti 2012

Aporta tu solución

Aportar una solución

Tu nombre (si quieres que aparezca):
Tu web/blog (si quieres que incluyamos un enlace a ella):
Tu e-mail (no se mostrará; si quieres que te avisemos cuando esté publicado):
¿Eres humano? ¿Cuánto es 3 menos dos?
Lenguaje
Fuente:

Ejemplo de solución en Java 

// Reto 012: La abuela binaria
// Propuesta de solución por Chiki
// 09-Ene-2014
 
import java.util.Scanner;
 
public class AbuelaBinaria {
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        int cantidad = sc.nextInt();
        for(int i=0; i<cantidad; i++) {
            int numero = sc.nextInt();
            System.out.println("Caso #" + (i+1) + ": " + numeroAvellanas(numero));
        }
    }
 
    public static int numeroAvellanas(int numero){
        int x = 0;
        int y = 0;
        int suma = -9999;
        int total = 0;
        for (int i = 0; i < numero; i++) {
            x = numero - i;
            y = i;
            total = devuelveCantidadBinario(x)+devuelveCantidadBinario(y);
            if(suma< total){
                suma = total;
            }
        }
        return suma;
    }
 
    public static int devuelveCantidadBinario(int numCantidad){
        int cantidad1 = 0;
        String numeroBinario="";
        while(numCantidad/2 != 0){
            numeroBinario += (numCantidad%2);
            numCantidad = (numCantidad/2);
        }
        numeroBinario+=numCantidad;
 
        for (int i = 0; i < numeroBinario.length(); i++) {
            if(String.valueOf(numeroBinario.charAt(i)).equals("1")){
                cantidad1++;
            }
        }
        return cantidad1;
    }
 
}