02-problem2.md

Problem 2

Kërkesa

Në një varg me numra natyrorë

$a_1, a_2, ... , a_n$

gjeni diferencën më të vogël të mundshme midis 2 prej tyre. Dmth gjeni vlerën minimale të

$|a_i - a_j|$

për çdo

$1 \leq i < j \leq n$

.

Referenca: https://www.codechef.com/problems/HORSES

Shembull

$ cat input.txt
1
5
4 9 1 32 13

$ python3 prog.py < input.txt
3

Zgjidhja 1

T = int(input())
for t in range(T):
    n = int(input())
    l = list(map(int, input().split()))
    dmin = abs(l[0] - l[1])
    i = 0
    while i <= n-2:
        j = i + 1
        while j <= n-1:
            d = abs(l[i] - l[j])
            if d < dmin:
                dmin = d
            j += 1
        i += 1
    print(dmin)

Sqarime

Marrim të gjitha kombinimet e mundshme të i dhe j, gjejmë diferencat midis tyre, dhe ndërkohë gjejmë edhe më të voglën e diferencave.

P.sh. për numrin

$a_1$

bëjmë diferencën me

$a_2, a_3, ... , a_n$

, për numrin

$a_2$

bëjmë diferencën me

$a_3, ... , a_n$

, e kështu me radhë.

Kjo zgjidhje nuk është dhe aq efiçente sepse për

$n$

numra duhet të bëjmë përafërsisht

$n^2$

veprime (zbritje, krahasime, etj.)

Zgjidhja më poshtë është më e shpejtë.

Zgjidhja 2

T = int(input())
for t in range(T):
    n = int(input())
    l = list(map(int, input().split()))
    l.sort(reverse=True)
    dmin = l[0] - l[1]
    i = 0
    while i <= n-2:
        d = l[i] - l[i+1]
        if d < dmin:
            dmin = d
        i += 1
    print(dmin)

Sqarime

Fillimisht i rendisim numrat në rendin zbritës. Pastaj, në vend që të bëjmë diferencën e numrit

$a_i$

me të gjithë numrat pasardhës, mjafton që të bëjmë diferencën e tij vetëm me numrin

$a_{i+1}$

, dhe dihet që diferenca me numrat e tjerë pasardhës nuk është më e vogël se kjo (sepse janë më të vegjël se

$a_{i+1}$

).

Detyra

Kemi një varg me numra ku të gjithë numrat përsëriten një numër çift herësh, me përjashtim të njërit i cili përsëritet një numër tek herësh. Të gjendet ky numër.

Referenca: https://www.codechef.com/problems/MISSP

Shembull

$ cat input.txt
2
3
1
2
1
5
1
1
2
2
3

$ python3 prog.py < input.txt
2
3

Janë 2 raste testimi, i pari ka 3 numra (njëri nën tjetrin), dhe i dyti ka 5 numra.