# 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