Finding the smartest set from an array of numbers

Question

Is there any way to make this program run in better time ? While running, it is taking 1 second for the sample test case to pass and 5-10 seconds for the rest of the test cases.

Problem statement

A smart-set is a set of distinct numbers in which all the elements have the same number of 1s in their binary form. The set of all smallest elements from each smart-set that can be formed from a given array of distinct positive numbers is known as the smartest-set.

So given an array of distinct numbers, outline the elements of the smartest-set in ascending sorted order.

Example

Let the array be {6 , 2 , 11 , 1 , 9 , 14 , 13 , 4 , 18}.

In binary form the set is {110, 010, 1011, 0001, 1001, 1110, 1101, 0100, 10010}.

The smart-sets are {1, 2, 4}, {6, 9, 18}, {11, 13, 14}.

The smartest-set is {1,6,11} as each element is the smallest element from each smart-set.

Input Format

The first line of input consists of an integer t. This is the number of test cases. For each test case, the first line of input contains an integer n. Here n is the number of elements in the array. The next line contains n space separated distinct integers which are the elements of the array.

Output Format

The output will space separated integer elements of the smartest-set in ascending order.

Constraints

0 < t < 1000 (This is the number of test cases )
2 < n < 10000 (This is the number of integer elements of the array) 
1 < Xi < 100000 (This is the size of each element of the array)
SAMPLE STDIN 1
3
9
6 2 11 1 9 14 13 4 18
3
7 3 1
3
1 2 4
SAMPLE STDOUT 
1 6 11
1 3 7
1

Code

test_case=input()
for case_num in range(int(test_case)):
 num_of_elements=input()
 arr=input()
 dictn={}
 #print (num_of_elements,arr)
 for bin_values in list(map(int,arr.split())):
 count=0
 for occurence in [int(x) for x in list('{0:0b}'.format(bin_values))]:
 if occurence==1:
 count=count+1
 dictn[bin_values]=count
 v = {}
 for key, value in sorted(dictn.items()):
 v.setdefault(value, []).append(key)
 lst=[]
 for key,value in (v.items()):
 x=min(value)
 lst.append(str(x))
 s= ' '
 s = s.join(lst)
 print (s)

Answer 1

Review

1. Don't print() but return variables, so other functions can reuse the outcome.
2. Split up your code into functions, for re usability and to easier test parts of your code.
3. Write test cases using the unittest module rather then doing it from the CLI every time

4. There are some code improvements as well,

   • You could benefit from the collections.defaultdict module
   • An easier way to count the "1" in the binaray format is: str(bin(ele)[2:]).count("1")
   • You can benefit from list or dict comprehension, see PEP202

Alternative

import unittest
from collections import defaultdict
def smartest_set(array):
 smart_sets = defaultdict(list)
 for element in array:
 num_of_ones = str(bin(element)[2:]).count("1")
 smart_sets[num_of_ones].append(element)
 # If you'd really want the output be printed, you can add a print statement in the function
 result = [min(e) for e in smart_sets.values()]
 print(result)
 return result
class Test(unittest.TestCase):
 def test_smartest_set(self):
 array = [6, 2, 11, 1, 9, 14, 13, 4, 18]
 expected = [1, 6, 11]
 self.assertEqual(expected, smartest_set(array))
 # More tests here...
if __name__ == "__main__":
 unittest.main()

Or a slightly faster approach storing the minimum value of the counts only

def smartest_set_2(array):
 smarts = {}
 for ele in array:
 num_of_ones = str(bin(ele)[2:]).count("1")
 smarts[num_of_ones] = min(ele, smarts.get(num_of_ones, float('inf'))
 return smarts.values()

• codaholic: It gave me this error: E ====================================================================== ERROR: test_smartest_set (main.Test) ---------------------------------------------------------------------- Traceback (most recent call last): File "test1.py", line 17, in test_smartest_set self.assertEqual(expected == smartest_set(array)) TypeError: assertEqual() takes at least 3 arguments (2 given) ---------------------------------------------------------------------- Ran 1 test in 0.031s FAILED (errors=1)
• Ludisposed: @codaholic Edited, my bad works now :)
• codaholic: I still don't have any idea where you are printing the output of the prgram
• Ludisposed: I currently don't, but you can call this function with any input and print it's results using, print(smartest_set([array]))
• Maarten Fabré: in the latest suggestion, you can prevent the if by doing smarts[num_of_ones] = min(ele, smarts.get(num_of_ones, float('inf'))