Bruteforce Algorithm to Find the Unique Positive Integer Whose S

  • 时间:2020-09-08 11:19:41
  • 分类:网络文摘
  • 阅读:115 次

Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0,
where each “_” is a single digit.

The “_” may not be the same digit. If it is the same digit, there is only 9 possible solutions, which you can just check one by one in O(1) time.

Bruteforce Algorithm to Find the Concealed Square

The Maximum possible square number is 192939495969798990 and the minimal square number is 1020304050607080900. The square root has to start with 1 and end with 0 so that the square number will start with 1 and end with zero.

Also, the last two digits should be 00 as any square numbers (more than two digit) will end with 00. This means our square number is 1_2_3_4_5_6_7_8_900. There fore we can just search the number that squares to 1_2_3_4_5_6_7_8_9 and multiple the original number by ten.

In order to end with 9, it has to be end with 7 or 3. Thus we can rule out the even numbers.

Thus, we compute the lower and upper bound, and do a bruteforce check for all the odd numbers between. The following Python code will take roughly half minute to run as it has 18946280 numbers to check. We convert the square number to string and use [::2] to pick up the digits in odd positions. Similarly we can use [1::2] to pick up the digits in the even positions.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from math import sqrt
 
def check(x):
    template = "1_2_3_4_5_6_7_8_9_0"
    if (len(str(x)) != len(template)):
        return False
    return str(x)[::2] == "1234567890"
 
low = int(sqrt(1020304050607080900))/10
high = int(sqrt(1929394959697989900))/10
 
for i in range(low, high + 1, 2):
    x = i * 10
    if check(x * x):
        print(x, x * x)
        break
from math import sqrt

def check(x):
    template = "1_2_3_4_5_6_7_8_9_0"
    if (len(str(x)) != len(template)):
        return False
    return str(x)[::2] == "1234567890"

low = int(sqrt(1020304050607080900))/10
high = int(sqrt(1929394959697989900))/10

for i in range(low, high + 1, 2):
    x = i * 10
    if check(x * x):
        print(x, x * x)
        break

The answer is 1389019170 and it squares to 1929374254627488900.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
都是马虎惹的祸作文100字  圣诞节的作文600字  春天的雨小学生作文  三下乡之七月十四号  打台球作文250字  龟兔赛跑数学问题  相遇后再追及的数学问题  小花在此次比赛中答错了几道题  原来四个数的平均数是多少  四面小旗子可组成几种不同的信号 
评论列表
添加评论