هيمنگ فاصلو ليٽ ڪوڊ حل  


تڪليف جي سطح آسان
بار بار پڇڻ ۾ ايڊوب Amazon ڪريو
algorithms بٽ مينپوليشن بٽس ڪوڊنگ انٽرويو انٽرويو جي تياري ليٽ ڪوڊ LeetCodeSolutions

مسئلي جو بيان  

ھن مسئلي ۾ ، اسان ٻن عددن کي ڏنل آھي اي ۽ بي ، ۽ مقصد ڳولڻ آھي هيمنگ فاصلو ڏنل انٽيگرز جي وچ ۾ انٽيگرز وڌيڪ آهن ته / برابر ۽ کان گهٽ 231   

مثال

First Integer = 5 , Second Integer = 2
3
First Integer = 4 , Second Integer = 5
1

هيمنگ فاصلو ليٽ ڪوڊ حلپن

نقطه نظر (بيٽنگ ڪندي بٽ کان)  

پهرين شيء جيڪا بلڪل واضح آهي اها آهي ته جڏهن کان اسان کي نمبر ڳولڻ جي ضرورت آهي مانين جتي ڏنل ٻن عددن ۾ ملندڙ ساٿي قدرون مختلف آهن ، اسان کي ڏنل انگ اکر جي bitwise XOR ڪرڻ گهرجن. نتيجا جيڪي XOR انفرادي بٽ واري پوزيشن ۾ پيدا ٿيندا ، جيڪڏهن '1' هجي ها ٻن انٽيگرن ۾ بٽس ان پوزيشن تي هئا مختلف. ٻي صورت ۾ ، XOR انهي پوزيشن تي '0' پيدا ڪندو.

هاڻي ته اسان هن حصي کي ختم ڪيو آهي ، صرف پيروي جي بچيل بيتن جي تعداد معلوم ڪرڻ جي لاءِ آهي مقرر (ساٿي قدر = '1') ڏنل عددن جي ساwiseي پاسي XOR ۾. هن قيمت کي ڳڻڻ لاءِ ، اسان هر بٽ جي لوپ ڪندا آهيون (تان جي طرف 30) ۽ چيڪ ڪريو ته ڇا XOR قيمت ۾ مقرر ٿيل آھي يا نه.

پڻ ڏسو
Rook Leetcode Solution لاءِ دستياب ڪيپچر

الورورٿم

  1. ھڪڙي عددي ۾ ٻٻرن عددن جي ساwiseي پاسي XOR ذخيرو ڪريو. xor_
  2. شروعاتي cnt = نتيجو ڪ storeڻ لاءِ
  3. هر لاء = = 0 ۽ مان <31:
    • جيڪڏهن 'ith'bit سيٽ ڪيو ويو آهي xor_
      • وڌايو سي اين ٽي: cnt ++ 
    • وڌايو i
  4. واپسي cnt

هيمنگ فاصله ليٽ ڪوڊ حل جو لاڳو

سي ++ پروگرام

#include <bits/stdc++.h>

using namespace std;

int hammingDistance(int x , int y){
    int xor_ = x ^ y , cnt = 0;
    for(int i = 0 ; i < 31 ; i++){
        if((1 << i) & xor_)
            cnt++;
    }
    return cnt;
}

int main(){
    int x = 5 , y = 2;
    cout << hammingDistance(x , y) << endl;
    return 0;
}

جاوا پروگرام

class hamming_distance{

    static int hammingDistance(int x , int y){
        int xor_ = x ^ y , cnt = 0;
        for(int i = 0 ; i < 31 ; i++){
            if(((1 << i) & xor_) > 0)
                cnt++;
        }
        return cnt;
    }

    public static void main(String args[]){
        int x = 5 , y = 2;
        System.out.println(hammingDistance(x , y));
    }
}
3

هيمنگ فاصلن Leetcode حل جو پيچيدگي تجزيو

وقت جي پيچيدگي

اي (1) جئين اسان انپاس کانسواءِ قطعي طور تي آپريشن جو انگ اکر انجام ڏيندا آهيون.

خلائي پيچيدگي

اي (1) جئين اسان مسلسل يادگيري جي جڳهه استعمال ڪندا آهيون.

نقطه نظر (بيٽنگ جي حساب سان موثر طريقي سان - ڪرنين جو الگورٿيم)  

پهريون قدم ساڳيو ئي رهي ٿو ، جيڪو ٽيو ڏنو نمبرن جي ساwiseي پاسي XOR ڳولڻ آهي. بهرحال ، اسان انهن جي XOR ۾ سيٽ بٽس جو تعداد موثر طريقي سان ڪورنائيگين جي الورگيتم استعمال ڪيو آهي ، جيڪو ان نظرئي تي ٻڌل آهي.

جڏهن اسان انجام ڏيندا آهيون “ٿورڙي ۽'هڪ انٽيگر جي وچ ۾ آپريشن 'مان' ۽ 'مان - 1'، انهي جو صحيح طور تي صحيح بيٽ آهي ختم نه ٿي.

اچو ته هڪ مثال ذريعي مٿي ideaاڻايل خيال جي پيروي ڪريون. غور ڪريو اين = 36 (100100) ھاڻي جيڪڏھن اسان '۽' اين - 1 سان ، اسين حاصل ڪريون ها:

اين & (اين - 1) = (36 & 35) = (100100 & 100011) = (100000) جيڪو صاف طور تي اڻ پورو ڪريو سا mostي بٽ (سا bitي طرف 2 واري جاءِ تي) ساڳي طرح ، اسان وڌيڪ لکي سگهون ٿا:

پڻ ڏسو
سال جو ڏينهن ليٽ ڪوڊ جو حل

اين ۽ (اين - 1) = (32 & 31) = (100000 & 011111) = 000000 جيڪو ٻيهر سا positionي طرف 5 تي صحيح ساٽ بٽ بي ترتيب ڪري ٿو. اهو عمل اڳتي جاري نه ٿو رکي سگھجي ڇاڪاڻ ته انٽيگر اين صفر ٿي ويو آهي.

هي سهڻو خيال ڪارآمد ثابت ٿيو ڳڻپ سيٽ بٽس انڌيري ۾ ، جئين اسان کي صرف ضرورت آهي اهو هلندڙ جيترا دفعا سيٽ بٽ آهن ڏنل انگ ۾

الورورٿم

  1. ھڪڙي عددي ۾ ٻٻرن عددن جي ساwiseي پاسي XOR ذخيرو ڪريو. xor_
  2. شروعاتي cnt = نتيجو ڪ storeڻ لاءِ
  3. جڏهن ته xor_ کان وڌيڪ آهي :
    1. وڌايو سي اين ٽي: cnt ++
    2. xor_ = xor_ ۽ (xor_ - 1) سيٽ ڪريو
  4. واپسي cnt

هيمنگ فاصله ليٽ ڪوڊ حل جو لاڳو

سي ++ پروگرام

#include <bits/stdc++.h>

using namespace std;

int hammingDistance(int x , int y){
    int xor_ = x ^ y , cnt = 0;
    while(xor_ > 0){
        xor_ = (xor_ & (xor_ - 1));
        ++cnt;
    }
    return cnt;
}

int main(){
    int x = 5 , y = 2;
    cout << hammingDistance(x , y) << endl;
    return 0;
}

جاوا پروگرام

class hamming_distance{

    static int hammingDistance(int x , int y){
        int xor_ = x ^ y;
        int cnt = 0;
        while(xor_ > 0){
            xor_ = (xor_ & (xor_ - 1));
            ++cnt;
        }
        return cnt;
    }

    public static void main(String args[]){
        int x = 5 , y = 2;
        System.out.println(hammingDistance(x , y));
    }
}
3

هيمنگ فاصلن Leetcode حل جو پيچيدگي تجزيو

وقت جي پيچيدگي

اي (1) جئين اسان انپاس کانسواءِ قطعي طور تي آپريشن جو انگ اکر انجام ڏيندا آهيون.

خلائي پيچيدگي

اي (1) جئين اسان مسلسل يادگيري جي جڳهه استعمال ڪندا آهيون.

1