makispaiktis

DCP338 - Same amount of 1's

Jul 23rd, 2021
1,107
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. '''
  2. Given an integer n, find the next biggest integer with the same number of 1-bits on.
  3. For example, given the number 6 (0110 in binary), return 9 (1001).
  4. '''
  5. from math import log2, log10
  6. from random import randrange
  7.  
  8. # Function 1 - Decimal to binary
  9. def decimalToBinary(decimal):
  10.     if decimal == 0:
  11.         return "0"
  12.     N = int(log2(decimal)) + 1
  13.     binary = []
  14.     for i in range(N - 1, -1, -1):
  15.         if decimal >= 2 ** i:
  16.             binary.append(str(1))
  17.             decimal -= 2 ** i
  18.         else:
  19.             binary.append(str(0))
  20.     return ''.join(binary)  # Return string
  21.  
  22. # Function 2 - Find the biggest integer with same 1's
  23. def findNearest(n):
  24.     binaryN = decimalToBinary(n)
  25.     length = len(binaryN)
  26.     # Now, I have to count the 1's
  27.     numberOf1s = 0
  28.     for ch in binaryN:
  29.         if ch == "1":
  30.             numberOf1s += 1
  31.     # So, having n, I will find the biggest number (all digits are 1s) that can be produced
  32.     # with the same "length"
  33.     biggest = 2**length - 1
  34.     if n == biggest:
  35.         return biggest, length, binaryN, binaryN
  36.     else:
  37.         for big in range(n+1, 1000):
  38.             binaryBig = decimalToBinary(big)
  39.             numberOfBig = 0
  40.             for ch in binaryBig:
  41.                 if ch == "1":
  42.                     numberOfBig += 1
  43.             if numberOfBig == numberOf1s:
  44.                 return big, numberOfBig, binaryN, binaryBig
  45.  
  46. # Function 3 - PrettyPrint
  47. def prettyPrint(n):
  48.     big, numberOfBig, binaryN, binaryBig = findNearest(n)
  49.     print("Input  = " + str(n) + " = " + str(binaryN))
  50.     print("Output = " + str(big) + " = " + str(binaryBig))
  51.     if n == big:
  52.         print("The 2 numbers are full of 1's")
  53.     else:
  54.         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.")
  55.     print()
  56.  
  57. # MAIN FUNCTION
  58. nList = list(range(5, 17))
  59. for n in nList:
  60.     prettyPrint(n)
RAW Paste Data