Algoritma Problemleri — 1

Girdi olarak sırasıyla:

• Dizinin uzunluğu (n) ve bir tam sayı (k),
• Birbirinden farklı n tane tam sayı veriliyor.

Çıktı olarak ise aşağıdaki şartı sağlayan en uzun alt kümenin uzunluğu isteniyor.

• Alt kümedeki herhangi iki sayının toplamı girdi olarak verilen k sayısına tam olarak bölünmemeli.

Örneğin: Sırasıyla 4, 3 ve {4, 3, 9, 1} girilmiş olsun. Burada yukarıdaki şartı sağlayan en uzun alt küme {4, 3, 1} veya {4, 9, 1} olacağından ve bu kümelerin uzunluğu 3 olduğundan sonuç 3 olacaktır. Çünkü 3 ve 9 sayıları aynı alt kümede bulunursa verilen k sayısına tam bölüneceğinden şart sağlanmaz.

Aşağıdaki çözüm bölümüne geçmeden önce soru üzerinde düşünmek isterseniz sorunun orijinal kaynağına buradan gidebilirsiniz. Çözümü düşünürken time complexity’nin O(n) olmasına dikkat edin.

Öncelikle girdilerimizi alacak kodu implemente edelim.

import java.util.*;

public class Solution {
    public static void main(String[] args)  {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] modulus = new int[k];
        for (int i = 0; i < n; ++i) {
            ++modulus[scanner.nextInt() % k];
        }
        scanner.close();

        int result = getNonDivisibleSubsetSize(k, modulus);
        System.out.println(result);
    }
}

Burada dizi için verilen sayıların k sayısına göre modunu alıp, çıkan sonucun indeksini bir artırıyorum. Yukarıdaki örnek için düşünecek olursak:

• 4 % 3 = 1 olduğundan modulus[1]+=1 yani modulus[1] -> 1
• 3 % 3 = 0 olduğundan modulus[0]+=1 yani modulus[0] -> 1
• 9 % 3 = 0 olduğundan modulus[0]+=1 yani modulus[0] -> 2
• 1 % 3 = 1 olduğundan modulus[1]+=1 yani modulus[1] -> 2

Örneğin k sayısının 4 verildiğini varsayalım. Bir sayının k sayısıyla olan modu 0, 1, 2, 3 olabilir. İstenilen alt kümeyi sağlamak için:

• Modu 0 olan sayılardan bu alt kümeye sadece bir tane dahil edilebilir. Çünkü bu sayı 4 (k) sayısının katı olacağından, bu sayının yanında bir başka 4 sayısının katının olması istenilen şartı bozar. Ayrıca 4 sayısının katları modu 1, 2 ve 3 olanlarla toplanıldığı zaman k sayısına bölümü tam olmayacağından istenilen şart sağlanmaya devam eder.
• Modu 1 olan sayılar modu 3 olan sayılarla birlikte bulunamaz. Çünkü bu sayılardan herhangi iki tanesinin toplamı k sayısına tam olarak bölünür. En uzun alt küme istenildiğinden bu iki sayı grubundan en çok olan alt kümeye dahil edilir.
• Modu 2 olan sayılar ise modu 0 olan sayılar ile aynı davranışı sergiler.

O halde bu örnek için şöyle bir yol izlenebilir:

1. 0. indeksin değeri 1den büyük veya 1e eşitse sonucu 1 artır.
2. 1. indeks ile (k–1). indeksin yani 3. indeksin değerlerini karşılaştır ve sonucu, büyük olan kadar artır.
3. 2. indeksin değeri 1den büyük veya eşitse sonucu 1 artır.

Eğer k sayısı 5 olursa yukarıdaki çözüm işe yarar mı? Evet. Mod sonuçları 0, 1, 2, 3, 4 olacağından bu sefer, 0. indeks tek başına ele alınır. 1. indeks ile 4. indeks, 2. indeks ile 3. indeks karşılaştırılır.

Şimdi adım adım kodumuzu implemente edelim.

private static int getNonDivisibleSubsetSize(int k, int[] modulus) {
    int result = 0;
    for(int i = 0; i <= k / 2; ++i) {

Sonucu tutmak için bir değişken tanımlıyorum. Döngüyü 0. indeksten başlatıp, birbirini tamamlayan değerleri kıyaslayacağım için k sayısının yarısına kadar devam ettiriyorum (2. maddeye bakınız).

int complement = (k - i) % k;

i. indeks ile kıyaslanacak indeksi belirlemek için bir değişken tanımlıyorum.

if (i == complement && modulus[i] >= 1) {
    result += 1;
}

Bu blok 0. indeks ve k sayısının yarısı kadar olan indekste (eğer k çift ise) çalışacaktır. Yukarıdaki örnekte (k sayısını 4 varsaydığımız) 1. ve 3. koşullar için çalışacaktır. Tabii ki indeksteki değer 1den büyük veya 1e eşit ise.

else {
    result += Math.max(modulus[i], modulus[complement]);
}

Bir üstteki durumlar dışında birbirini tamamlayan sayı gruplarından büyük olanı sonuca ekliyoruz.

}
    return result;
}

Ve sonucu dönüyoruz :)

Bu ve bunun gibi birçok sorunun çözümünün olduğu github repository’me buradan ulaşabilirsiniz.