[Codility] 3. Complexity

3.1 FrogJmp

A small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to a position greater than or equal to Y. The small frog always jumps a fixed distance, D.
Count the minimal number of jumps that the small frog must perform to reach its target. Write a function that, given three integers X, Y and D, returns the minimal number of jumps from position X to a position equal to or greater than Y.

작은 개구리 한 마리가 도로의 다른 쪽으로 가고 싶어합니다. 그 개구리는 현재 X 위치에 있고 Y보다 크거나 같은 위치로 가고 싶어합니다. 그 작은 개구리는 항상 일정한 거리인 D를 점프합니다.
작은 개구리가 목표에 도달하기 위해 수행해야 하는 최소 점프 횟수를 세십시오.
세 개의 정수 X, Y, D가 주어졌을 때 X 위치에서 Y와 같거나 더 큰 위치로 점프하는 최소 횟수를 반환하는 함수를 작성합니다.

import math
def solution(X, Y, D):
    return math.ceil((Y-X)/D)

3.2 PermMissingElem

An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.
Your goal is to find that missing element.

Write a function that, given an array A, returns the value of the missing element.

Write an efficient algorithm for the following assumptions:
N is an integer within the range [0..100,000];
the elements of A are all distinct;
each element of array A is an integer within the range [1..(N + 1)].

 

N개의 서로 다른 정수로 구성된 배열 A가 주어집니다. 배열은 [1..(N + 1)] 범위의 정수를 포함하는데, 이것은 정확히 한 개의 원소가 빠져 있다는 것을 의미합니다.
당신의 목표는 그 누락된 요소를 찾는 것입니다.

배열 A가 주어지면 누락된 요소의 값을 반환하는 함수를 작성합니다.

다음 가정을 위한 효율적인 알고리즘을 작성합니다:
N은 [0..100,000] 범위 내의 정수입니다;
A의 요소는 모두 구별됩니다;
배열 A의 각 요소는 [1..(N + 1)] 범위 내의 정수입니다.

def solution(A):
    N = len(A)
    return ( (N+1)*(N+2))//2 - sum(A)

3.3 TapeEquilibrium

A non-empty array A consisting of N integers is given. Array A represents numbers on a tape.
Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].
The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|
In other words, it is the absolute difference between the sum of the first part and the sum of the second part.
Write a function that, given a non-empty array A of N integers, returns the minimal difference that can be achieved.

N개의 정수로 구성된 비어 있지 않은 배열 A가 주어집니다. 배열 A는 테이프의 숫자를 나타냅니다.
0 < P < N 등의 정수 P는 이 테이프를 A[0], A[1], ..., A[P], A[P + 1] 및 A[P], A[P + 1], ..., A[N - 1]의 두 개의 비어 있지 않은 부분으로 분할합니다.
두 부품의 차이는 |(A[0] + A[1] + ... + A[P - 1]) - (A[P] + A[P + 1] + ... + A[N - 1]) |
즉, 첫 번째 부분의 합과 두 번째 부분의 합의 절대적인 차이입니다.
N개의 정수로 이루어진 비어 있지 않은 배열 A가 주어졌을 때 얻을 수 있는 최소 차이를 반환하는 함수를 작성합니다.

 

def solution(A):
    left = A[0]
    right = sum(A[1:])
    mn = abs(left-right)
    for i in range(1, len(A)-1):
        left+=A[i]
        right-=A[i]
        tmn = abs( left - right )
        if mn >= tmn:
            mn = tmn
    return mn