Challenge: Talk in Binary

Lab Java Beginner 10 points

Print the binary form of n using recursion (don't use Integer.toBinaryString). Hint: the binary of n is the binary of n / 2 followed by the digit n % 2.

Input

One whole number n (0 ≤ n ≤ 10⁹).

Output

n in binary.

Example

Input

Output

Sample input available Sample output available

Editor

Java

Hints

Base case: 0 and 1 are just "0" and "1".

binary(n) = binary(n / 2) + (n % 2).

Solution explanation

Each call halves n, so there are about log₂(n) calls – 30 for a billion.

Show solution

import java.util.Scanner;

public class Main {
    static String binary(int n) {
        if (n < 2) return String.valueOf(n);
        return binary(n / 2) + (n % 2);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println(binary(sc.nextInt()));
    }
}

Output

Answer