体面数字| 帮助减少时间复杂性

Question

HackerRank问题陈述

我必须找到具有'N'数字的最大"正确数字".Decent Number具有以下属性:

=> 3, 5, or both as its digits. No other digit is allowed.
=> Number of times 3 appears is divisible by 5.
=> Number of times 5 appears is divisible by 3.

我的代码完美无缺!但我担心它远没有效率:

输入:

4 #number of test cases, i.e., the following 4 inputs
1
3
5
11

输出:

-1
555
33333
55555533333

我的解决方案版本:

T = int(input()) #number of test cases

def computePair(N):
    multiplesOf3 = [i for i in range(N+1) if i%3 == 0]
    if multiplesOf3 != [0]: #reversing a [0] results in a 'NoneType'
        multiplesOf3.reverse()
    multiplesOf5 = [i for i in range(N+1) if i%5 == 0]

    for i in multiplesOf3:
        for j in multiplesOf5:
            if (i+j) == N:
                return (i, j)
    return -1

for testCase in range(T):
    N = int(input()) #test case
    result = computePair(N)
    if result == -1:
        print(result) #If no such combination exists return '-1'
    else:
        print('5' * (result[0]) + '3' * (result[1]))

我假设我的代码的时间复杂度为O(n ^ 2); 因为2'for'循环.我希望它以O(n) - 线性的顺序更有效.

这是一个非常通用的问题:另外,您是否有时间复杂度最佳实践的资源？我很糟糕.

Answer 1

要解决这个问题,我们需要做一些观察:

• the largest "decent number" having 'N' digits 是包含最多数字5的数字.它将具有5555 ... 3333的形式...

• 至于Number of times 5 appears is divisible by 3,我们有三种情况:

  • 如果N除以3,则没有数字3.

  • 如果N % 3 = 1,所以我们需要a times在结果中添加数字3,a % 3 == 1并使数字5的总数(N - a)可被3整除,所以a % 3 == 1和a % 5 == 0- > a = 10.(请注意,a所有有效值中必须是最小的).最终结果的(N - 10)数字为5,10数字为3.

  • 同样,如果N % 3 = 2,所以我们需要a times在结果中添加数字3,a % 3 == 2并且a % 5 == 0- > a = 5;

通过这些观察,您可以在O(1)中为每个N解决此问题.