Topics are as follows

See a solution using 01 knapsack idea, the code is very concise, link here

https://blog.csdn.net/bing_lee/article/details/77899602

 

Talk about my thoughts

1. The main purpose of this paper is to find out whether there is a combination K in the set M consisting of the numbers on each bit of the number so that sum(K)== sum(M)/2 exists.

2 When Max (M) > sum(M)/2 is the maximum value in M, then the number can not be a magic number, such as 1119.

3 Starting from the first element of M, we recursively find the target combination K, prune the impossible combination in time, and avoid redundant recursive calculation.

4 Reproduce M', a subset of M, recursively and shallowly, and remove the currently selected elements

5 Find the combination K of sum (K) === sum (M) / 2 and return to True

6 When the number of elements in M'is 0, return False

import time
def run(a,b):
    sum = 0
    for i in range(a,b):
        if check(i):
            sum += 1
    return  sum


def num2array(n):
    n_str = str(n)
    length = len(n_str)
    arr = []
    for i in range(length):
        arr.append(int(n_str[i]))
    arr.sort()
    return arr


def check(n):
    n_arr = num2array(n)
    a = sum(n_arr)
    # Even numbers can be magic numbers
    if a % 2 == 0:
        half = int(a / 2)
        max_item = max(n_arr)
        if max_item > half:
            return False
        else:
            if max_item == half:
                return True
            else:
                return  handler(n_arr,0,half)




def handler(arr,sum,half):
    length = len(arr)
    if length == 0:
        return False
    for k in arr:
        tmp_sum = sum + k
        if tmp_sum == half:
            return True
        else:
            if tmp_sum > half:
                continue
            else:
                arr1 = arr[:]
                arr1.remove(k)
                if handler(arr1,tmp_sum,half):
                    return True

a = 1
b = 65535
start = time.time()
sum = run(a,b)
end = time.time()
print('Share:%d Magic number,Detection time consuming%.2f s' % (sum,end-start))

Operation result

Total: 19977 magic numbers, detection time 0.66 s

python is a glue language with powerful functions and slow speed. It is estimated that C/C++ will be better to achieve the 1s execution required by Jingdong.
 

Reflection

When the input interval span is very large, there will be many repeated calculations. For example, the detection tasks of 11113111 and 3111111111 are the same, but they have been detected many times.

Let's consider a Resume Result Dictionary D to store ordered numbers, such as the key s of both numbers are 111111113.

Before checking whether it is a magic number, we first check whether there is a key in dictionary D, and then return it directly without further checking. If the result is a magic number, we add a dictionary.

The code is as follows

import time

class MagicNumber:

    __dict = {}

    def run(self,a,b):
        sum = 0
        for i in range(a,b):
            if self.check(i):
                sum += 1
                # print(i)
        return  sum


    def num2array(self,n):
        n_str = str(n)
        length = len(n_str)
        arr = []
        for i in range(length):
            arr.append(int(n_str[i]))
        arr.sort()
        return arr


    def check(self,n):
        n_arr = self.num2array(n)
        a = sum(n_arr)
        # Even numbers are capable of becoming magic numbers
        if a % 2 == 0:
            half = int(a / 2)
            max_item = max(n_arr)
            if max_item > half:
                return False
            else:
                key = self.array2string(n_arr)
                if key in self.__dict:
                    return  True
                if max_item == half:
                    self.__dict[key] = 1
                    return True
                else:
                    re = self.handler(n_arr,0,half)
                    if re:
                        self.__dict[key] = 1
                    return  re

    def array2string(self,arr):
        string = ''
        for i in arr:
            string += str(i)
        return  string


    def handler(self,arr,sum,half):
        # In the end, it's not satisfied.
        length = len(arr)
        if length == 0:
            return False
        for k in arr:
            tmp_sum = sum + k
            if tmp_sum == half:
                return True
            else:
                if tmp_sum > half:
                    continue
                else:
                    arr1 = arr[:]
                    arr1.remove(k)
                    if self.handler(arr1,tmp_sum,half):
                        return True

    def get_dict(self):
        return self.__dict

a = 1
b = 1000000
start = time.time()
c = MagicNumber()
sum = c.run(a,b)
end = time.time()
print('Share:%d Magic number,Detection time consuming%.2f s' % (sum,end-start))

65535 data checking times also increased

Total: 19977 magic numbers, detection time 0.73 s

The number of 100 W checked for 20 seconds. I don't know who can give a C run time.

Total: 376413 magic numbers, detection time 20.13 s econds
There is also a problem here. Resume dictionaries are time-consuming, but I think that with the increase of input intervals, the advantages of dictionaries will gradually emerge.

 

PS Personal Computer Configuration