Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

  • Binary Representation of Numbers

    We have been working with integers for quite a while. But how are they actually represented in our computers? We know that everything on our machines is either 0 or 1. So, all the integers are represented in some form that is stored as a sequence of 0s and 1s. We call that the binary representation of numbers.
    Any number can be represented as a sum of powers of 2 (1, 2, 4, 8, 16, 32, …):
    • 19 = 16 + 2 + 1
    • 20 = 16 + 4
    • 140 = 128 + 8 + 4
    Therefore, we can create a sequence of 0s and 1s that would represent the powers of 2, and to get the final number, we would just add those up together. In case the representation contains 1 - we include the corresponding power of 2, and in case it’s a 0 - we exclude it. For 140 we included the 128, 8, and 4 powers of 2 while excluding 64, 32, 16, 2, and 1. We can do that for any number:
    Power of 2
    Power of 2 in decimal
    512
    256
    128
    64
    32
    16
    8
    4
    2
    1
    Binary (include/exclude)
    0
    1
    0
    0
    1
    1
    0
    1
    1
    1
    Sum (311)
    311
    311
    55
    55
    55
    23
    7
    7
    3
    1
    The convention is to write the small powers of 2 on the right, and progress to larger ones as we move to the left. So, we first start from 1, then process 2, then 4, etc.
    Starting from the rightmost power of 2 we sum up all the powers of 2 that have a 1 in the binary representation and obtain the final number.

    Challenge

    Given a binary representation, you are asked to write a program to print the original number.

    Input

    The only line of the input contains the string s of 0s and 1s (1 ≤ |s| ≤ 31).

    Output

    The program should print the actual number.

    Examples

    Input
    Output
    0100110111
    311
    101
    5
    110
    6
    111
    7
     

    Constraints

    Time limit: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue