DCP338 - Same amount of 1's

'''
Given an integer n, find the next biggest integer with the same number of 1-bits on.
For example, given the number 6 (0110 in binary), return 9 (1001).
'''
from math import log2, log10
from random import randrange

# Function 1 - Decimal to binary
def decimalToBinary(decimal):
    if decimal == 0:
        return "0"
    N = int(log2(decimal)) + 1
    binary = []
    for i in range(N - 1, -1, -1):
        if decimal >= 2 ** i:
            binary.append(str(1))
            decimal -= 2 ** i
        else:
            binary.append(str(0))
    return ''.join(binary)  # Return string

# Function 2 - Find the biggest integer with same 1's
def findNearest(n):
    binaryN = decimalToBinary(n)
    length = len(binaryN)
    # Now, I have to count the 1's
    numberOf1s = 0
    for ch in binaryN:
        if ch == "1":
            numberOf1s += 1
    # So, having n, I will find the biggest number (all digits are 1s) that can be produced
    # with the same "length"
    biggest = 2**length - 1
    if n == biggest:
        return biggest, length, binaryN, binaryN
    else:
        for big in range(n+1, 1000):
            binaryBig = decimalToBinary(big)
            numberOfBig = 0
            for ch in binaryBig:
                if ch == "1":
                    numberOfBig += 1
            if numberOfBig == numberOf1s:
                return big, numberOfBig, binaryN, binaryBig

# Function 3 - PrettyPrint
def prettyPrint(n):
    big, numberOfBig, binaryN, binaryBig = findNearest(n)
    print("Input  = " + str(n) + " = " + str(binaryN))
    print("Output = " + str(big) + " = " + str(binaryBig))
    if n == big:
        print("The 2 numbers are full of 1's")
    else:
        print("The 2 numbers have " + str(numberOfBig) + " 1's. " + str(big) + " is the lowest number of the greater ones of " + str(n) + " with the same amount of 1's.")
    print()

# MAIN FUNCTION
nList = list(range(5, 17))
for n in nList:
    prettyPrint(n)