How to efficiently find Finding the smartest set from an array of numbernumbers

Is there any way to make this program run in better time because while? 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. Please find below the explained problem

added 41 characters in body; edited tags; edited title

Source Link

edited Jun 23, 2018 at 5:28

Phrancis

20.4k
6
68
154

How to efficiently Findfind the smartest set from an array of number

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.

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.

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

    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.

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.

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

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

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

How to efficiently Find the smartest set from an array of number

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.

    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.

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.

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

How to efficiently find the smartest set from an array of number

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.

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.

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.

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

Source Link

asked Jun 23, 2018 at 5:14

codaholic

185
6

How to efficiently Find the smartest set from an array of number

Is there any way to make this program run in better time because 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. Please find below the explained problem

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)

python

Stack Exchange Network

Return to Question

How to efficiently find Finding the smartest set from an array of numbernumbers

How to efficiently find the smartest set from an array of number

Finding the smartest set from an array of numbers

How to efficiently Findfind the smartest set from an array of number

How to efficiently Find the smartest set from an array of number

How to efficiently find the smartest set from an array of number

How to efficiently Find the smartest set from an array of number