Təkrarlanmayan elementin tapılması (Lonely Integer)

HackRank`da qarşıma maraqlı bir məsələ çıxdı. Deməli məsələnin şərti belə idi ki, bir massiv verilib və bu massivdə bir elementdən başqa bütün elementlər cüt-cüt təkrarlanır. Bizdən təkrarlanmayan həmin elementi tapmaq tələb olunur (daha ətraflı). Nümunə kimi göstərsək input və output aşağıdakı kimi olmalıdır:

Məsələnin çox maraqlı həll variantı var idi, özüm üçün də yeni idi. Çox maraqlı gəldiyi üçün blogda da paylaşmaq qərarına gəldim. Deməli məsələni cəmi bir dövr ilə O(n) zamanda həll etmək mümkündür. Exclusive Or (bitwise XOR) operatorunun bu məsələnin həllində nə dərəcədə faydalı olduğunu görəcəksiniz. Şəxsən mən çox təəccübləndim 🙂 Bu operator haqqında Java’ya başlayanda, sertifikat imtahanına hazırlaşanda çox oxumuşuq, amma praktik baxımdan belə bir məsələnin həllində önəmli bir rol oynayacağı ağlıma gəlməmişdi. Nə isə çox danışdıq, keçək kodunu yazmağa 🙂

package az.mm.algoritms;

public class LonelyInteger {

public static void main(String[] args) {
    int[] arr = {1, 2, 1, 3, 2, 4, 3};

    /*
    //test uchun
    arr = new int[]{1, 1, 2};
    arr = new int[]{0, 0, 1, 2, 1};
    arr = new int[]{4, 5, 7, 6, 4, 7, 5, 8, 8};
    */

    System.out.println(getLonelyInteger(arr));
}

public static int getLonelyInteger(int[] arr) {
    int unique = 0;
    for (int i : arr) 
        unique ^= i;

    return unique;
}
}

İndi işin daha maraqlı hissəsinə keçək. Bəs bu kod necə işləyir?

Bildiyimiz kimi bitwise operatorlar həm boolean, həm də Integer dəyərləri müqayisə edir. Bizim nümunəmizdə Integer dəyərlər müqayisə ediləcək. Onluq say sistemində olan ədədlər əvvəlcə ikilik say sisteminə çevirilir və sonra müqayisə edilir. Daha anlaşıqlı olması üçün metodumuza print ifadələr əlavə edək, yuxarı qeyd olunan massiv üçün run edək və output üzərindən izahımıza davam edək:

public static int getLonelyInteger(int[] arr) {
    int unique = 0;
    System.out.print(unique + "("+Integer.toBinaryString(unique)+")");
    for (int i : arr){ 
        System.out.print(" ^ " + i + "("+Integer.toBinaryString(i)+")");
        unique ^= i;
    } 

    return unique;
}

Output:

• 0(0) ^ 1(1) ^ 2(10) ^ 1(1) ^ 3(11) ^ 2(10) ^ 4(100) ^ 3(11)

Output’da massivin elementləri və mötərizədə onların ikilik say sistemindəki qarşılıqları verilib. Müqayisənin rahat aparılması üçün 3 simvoldan az olan ikilik saylarımızın qarşısını sıfırlarla dolduraq və 3 simvola tamamlayaq. Və beləliklə, bizim bütün kodumuzun canı aşağıdakı ifadədə olacaq:

• 000 ^ 001 ^ 010 ^ 001 ^ 011 ^ 010 ^ 100 ^ 011

Bitwise XOR operatoru bit bit müqayisə aparır və müqayisə olunan tərəflər fərqlidirsə 1, digər bütün hallarda isə 0 qaytarır:

Bu operatorun özəlliyi ondan ibarətdir ki, təkrarlanan (daha dəqiq cüt) dəyərləri sıfırlayır. Və bu problemin həllində tətbiq olunma səbəbi də budur. Təkrarlanan  elementlər sıfırlandıqda biz rahatlıqla təkrarlanmayan (unique) elementi tapa bilərik. Müqayisəni hissə-hissə aparaq və qeyd etdiklərimizi əyani olaraq görək:

• 000 ^ 001 ^ 010 ^ 001 ^ 011 ^ 010 ^ 100 ^ 011
001 ^ 010 ^ 001 ^ 011 ^ 010 ^ 100 ^ 011
011 ^ 001 ^ 011 ^ 010 ^ 100 ^ 011
010 ^ 011 ^ 010 ^ 100 ^ 011
001 ^ 010 ^ 100 ^ 011
011 ^ 100 ^ 011
111 ^ 011
100

100-ün onluq say qarşılığı 4 ədədidir və 4 ədədi bizim massivimizdə təkrarlanmayan elementdir.

Bitwise XOR operatoru istifadə etmədən bu problemi necə həll etmək olar?

Counting Sort alqoritmini oxuyarkən oradakı sayma məntiqi diqqətimi çəkmişdi və fikirləşdim həmin sayma məntiqini bu problemə də tətbiq etmək olar. Həmin sayma məntiqi necə işləyir, qısaca qeyd edək:

Əlavə bir massiv yaradılır, adına sayma massivi deyək. Orijinal massivdəki elementlərin dəyəri sayma massivində həmin dəyərə uyğun gələn indekslərdə saxlanılır. Tutaq ki, orijinal massivdə 0-cı indeksin dəyəri 2-dirsə, sayma massivində 2-ci indeksə 1 yazılır. Əgər orijinal massivdə 2 dəyərinə sahib başqa element varsa, o zaman sayma massivində 2-ci indeksin dəyəri 1 vahid artırılır.

Bu sayma üsulunun mənfi yönləri var, orijinal massivdə elementlər arasında dəyər fərqləri böyük olduqda daha çox yaddaş sərf edir, çünki sayma massivinin uzunluğu orijinal massivin ən böyük dəyərə malik elementindən bir vahid böyük olmalıdır. Amma bizim məsələnin şərtində qeyd olunur ki, elementlərin dəyəri 0 və 100 arasında olmalıdır, bu da elə böyük rəqəm deyil. O səbəbdən yaddaş məsələsində çox dərinə getməyəcəyik. getLonelyInteger(int[] ) metodumuzu fərqli formada yenidən kodlaşdıraq:

public static int getLonelyInteger(int[] arr) {
    int unique = 0;
    int[] k = new int[101];  // sayma massivimiz
    for (int i=0; i<arr.length; i++)
        k[arr[i]]++;

    for (int i=0; i<k.length; i++) 
        if(k[i] == 1) return i;

    return unique;
}

Birinci dövr ilə hansı dəyərin neçə vahid olduğunu sayırıq, ikinci dövr ilə isə sayma massivində dəyəri (yəni sayı) 1-ə bərabər olan indeksi tapırıq. Kodumuzun performansı (complexity) təxminən O(k+n)-dir.

Bu mövzu da bu qədər 🙂 Ümid edirəm faydalı olmuşdur. Uğurlar!