cassidoo-1216.py

binary-by-queue.py

# Given a positive number N, generate binary numbers between 1 to N using a queue-type structure in linear time.

# Example:
# > binaryQueue(10)
# > 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 10000

import math

def printBinary(queue):
    foundOne = False
    queueString = ''
    for i in range(len(queue)):
        if queue[i] == 1:
            foundOne = True
        if foundOne:
            queueString += str(queue[i])
    return(queueString)

def flipBit(queue, q):
    if queue[q] == 0:
        queue[q] = 1
    else:
        queue[q] = 0
        flipBit(queue, q - 1)
    return

def binaryQueue(N):
    queueSize = math.ceil(math.log(N,2))
    queue = [0] * queueSize
    q = len(queue) - 1
    output = ''
    for i in range(N):
        flipBit(queue, q)
        output += printBinary(queue) + ' '
    print(output)
    return

binaryQueue(10)