하나의 크기 변수 N이 있다고 가정하고, 하나의 변수 SUM도 있다고 가정합니다. 이것은 배열에서 사용 가능한 모든 요소의 총합이고 배열에 요소가 없는 다른 변수 K는 다음과 같습니다. K보다 크면 배열의 모든 요소가 구별되는 하나의 직교 배열을 찾아야 합니다. 솔루션이 없으면 -1을 반환합니다.
따라서 입력이 N =4, SUM =16 K =9와 같으면 출력은 [1,2,4,9]
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
minimum_sum :=(N *(N + 1)) / 2
-
maximum_sum :=(N * K) -(N *(N - 1)) / 2
-
minimum_sum> SUM 또는 maximum_sum
-
반환 -1
-
-
res :=크기가 N + 1인 배열 하나와 0부터 N까지 채우기
-
합계 :=minimum_sum
-
나는 :=N
-
i>=1인 동안 수행
-
x :=합계 + (K - i)
-
x
-
합계 :=합계 +(K - i)
-
res[i] :=K
-
K :=K - 1
-
-
그렇지 않으면
-
res[i] :=res[i] +(SUM - 합계)
-
합계 :=합계
-
루프에서 나오다
-
-
나는 :=나는 - 1
-
-
반환 해상도
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def get_arr(N, SUM, K): minimum_sum = (N * (N + 1)) / 2 maximum_sum = (N * K) - (N * (N - 1)) / 2 if (minimum_sum > SUM or maximum_sum < SUM): return -1 res = [i for i in range(N + 1)] sum = minimum_sum i = N while(i >= 1): x = sum + (K - i) if (x < SUM): sum = sum + (K - i) res[i] = K K -= 1 else: res[i] += (SUM - sum) sum = SUM break i -= 1 return res N = 4 SUM = 16 K = 9 print(get_arr(N, SUM, K))
입력
4, 16, 9
출력
[0, 1, 2, 4.0, 9]