[HackerRank] Divisible Sum Pairs (PYTHON)

문제 링크 : https://www.hackerrank.com/challenges/divisible-sum-pairs/problem

Divisible Sum Pairs | HackerRank

O(n²) 의 시간복잡도를 가진다.

def divisibleSumPairs(n, k, ar):
    # Write your code here
    cnt = 0 
    for i in range(len(ar)):
        for j in range(i+1,len(ar)):
            if (ar[i] + ar[j]) % k == 0:
                cnt += 1
    return cnt

개선된 코드

def divisibleSumPairs(n, k, ar):
    # Write your code here
    cnt = 0 
    for i in range(len(ar)):
        j = i + 1
        while j < n:
            if (ar[i] + ar[j]) % k == 0:
                cnt += 1
            j += 1
    return cnt

O(N)으로 만드는 로직을 생각하는게 중요한듯 합니다.