14:01
LeetCode 3116: 'Hard' problemi ikili axtarış və daxilolma-xaricetmə ilə necə asanlaşdırmaq olar?
LeetCode üzərindəki "Kth Smallest Amount With Single Denomination Combination" problemi (nömrə 3116) son vaxtlar proqramçılar arasında müzakirə olunur. Rəsmi olaraq "Hard" səviyyəsində qiymətləndirilən bu problem, qəbul nisbətinin cəmi 26% olması ilə diqqət çəkir. Bəs niyə bu qədər az adam düzgün həll tapa bilir?
Əsas səbəb odur ki, bir çox proqramçı birbaşa yanaşma – yəni bütün qatlarını yaratmaq və k-cı ən kiçik elementi seçmək – üzərində dayanır. Lakin bu üsul işləmir, çünki k dəyəri 2×10⁹-a qədər çıxa bilir. Bu, sadəcə olaraq çox böyük rəqəmdir və adi generasiya metodları vaxt və yaddaş baxımından iflasa uğrayır.
Doğru yanaşma isə ikili axtarış (binary search) və daxilolma-xaricetmə (inclusion-exclusion) prinsipinə əsaslanır. Məntiq belədir: axtardığınız X cavabını təxmin edirsiniz, sonra X'dən kiçik və ya bərabər olan neçə uyğun ədəd olduğunu hesablayırsınız. Bu sayı (count(X)) monotonikdir – yəni X artdıqca say da artır. Monotonik funksiyalar isə ikili axtarış üçün idealdır.
Problemin ən çətin hissəsi count(X) funksiyasını düzgün yazmaqdır. Burada daxilolma-xaricetmə prinsipi işə düşür: verilən nominalların kombinasiyalarından yaranan ədədlərin sayını tapmaq üçün ümumi çoxluqdan kəsişmələri çıxmaq lazımdır. Tam izahı və kod nümunəsi üçün bu video dərsliyə baxa bilərsiniz.
Bu yanaşma təkcə LeetCode 3116 üçün deyil, ümumiyyətlə "k-cı ən kiçik element" tipli problemlərdə işinizə yarayacaq. Azərbaycanlı proqramçılar üçün bu tip alqoritmik məntiqi mənimsəmək, intervyu mərhələlərində və müsabiqələrdə böyük üstünlük verir. Qeyd edək ki, oxşar problemlərə "Google", "Meta" və digər iri texnologiya şirkətlərinin müsahibələrində tez-tez rast gəlinir.
Xülasə, əgər LeetCode 3116 ilə mübarizə aparırsınızsa, birbaşa həll axtarmaq əvəzinə, ikili axtarış və daxilolma-xaricetmə kombinasiyasını sınayın. Bu, problemi "Hard"dan "Medium" səviyyəsinə endirə bilər.