校招真题练习002 被3整除(网易)

左手的ㄟ右手 2021-12-19 04:23 255阅读 0赞

[被3整除][3]

小Q得到一个神奇的数列: 1, 12, 123,...12345678910,1234567891011...。  
并且小Q对于能否被3整除这个性质很感兴趣。  
小Q现在希望你能帮他计算一下从数列的第l个到第r个(包含端点)有多少个数可以被3整除。

输入描述:  
输入包括两个整数l和r(1 <= l <= r <= 1e9), 表示要求解的区间两端。  
输出描述:  
输出一个整数, 表示区间内能被3整除的数字个数。

1 inputval = list(map(int,input().split()))
     2 low,high = inputval[0],inputval[1]
     3 cnt = 0
     4 if (high - low) // 3 <= 1:
     5     for i in range(low,high+1):
     6         y = i % 3
     7         if y == 1:
     8             cnt += 0
     9         elif y == 0:
    10             cnt += 1
    11         else:
    12             cnt += 1
    13 else:
    14     z = (high - low) // 3
    15     z1 = (high - low + 1) // 3
    16     z2 = (high - low + 1) % 3
    17     if z2 == 0:
    18         cnt = z1 * 2
    19     else:
    20         l = low % 3
    21         if l == 1 or l == 2:
    22             cnt += 2
    23         elif l == 0:
    24             cnt += 1
    25         h = high % 3
    26         if h == 1:
    27             cnt += 0
    28         elif h == 2:
    29             cnt += 1
    30         else:
    31             cnt += 2
    32         cnt += (z-1) * 2
    33 print(cnt)

题目类型：数学

算法思想：位数 % 3有三种取值，

值为1:不能整除，值为2:可以被整除，值为0:可以被整除。

因此在low到high之间，以3个为一组，每组中有2个可以被3整除。再处理一下边缘值即可。

转载于:https://www.cnblogs.com/asenyang/p/11095096.html

[3]: https://www.nowcoder.com/practice/51dcb4eef6004f6f8f44d927463ad5e8?tpId=98&tqId=32825&tPage=1&rp=1&ru=/ta/2019test&qru=/ta/2019test/question-ranking