පරාසයේ විශාලතම අමුතු බෙදුම්කරුගේ XOR පිළිබඳ විමසීම්


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ 24 * 7 නවෝත්පාදන විද්‍යාගාර සිටඩෙල් ඩිරෙක්ටි Expedia ගූගල් ඇත්ත වශයෙන්ම Snapdeal
අරා බිටු Bitwise-XOR විමසුම් ගැටළුව

ගැටළු ප්රකාශය

“පරාසයේ විශාලතම අමුතු බෙදුම්කරුගේ XOR පිළිබඳ විමසීම්” ගැටලුවේ සඳහන් වන්නේ ඔබට ලබා දී ඇති බවයි අරාව of නිඛිල q විමසුම, සෑම විමසුමක්ම පරාසයකින් සමන්විත වේ. එක් එක් විමසුම සඳහා ලබා දී ඇති පරාසය තුළ ඇති විශාලතම අමුතු බෙදුම්කරුගේ XOR සොයා ගැනීමට ගැටළු ප්‍රකාශය ඉල්ලා සිටී.

උදාහරණයක්

arr[] = {2, 6, 4}
Query :(1, 2), (0, 1)
2 2

පැහැදිලි කිරීම

ශ්‍රේෂ් est තම අමුතු බෙදුම්කරු: (1,3,1)

3,1 හි XOR 2 වේ.

1,3 හි XOR 2 වේ.

පරාසයේ විශාලතම අමුතු බෙදුම්කරුගේ XOR පිළිබඳ විමසීම්

 

ඇල්ගොරිතම

  1. දී ඇති අරාව හරහා ගමන් කරන්න.
    1. අරාවෙහි වත්මන් මූලද්‍රව්‍යය අමුතු දැයි පරීක්ෂා කර බලා වත්මන් මූලද්‍රව්‍යය අවම බෙදුම් අංකය මගින් යාවත්කාලීන කරන්න.
    2. සකසන්න divArray දී ඇති අරාවක යාවත්කාලීන අංගයට මූලද්‍රව්‍යය.
  2. අරාව නැවත ගමන් කර, එක් එක් අංග යාවත්කාලීන කරන්න divArray වත්මන් මූලද්‍රව්‍යයේ XOR වෙත අරාව සහ divArray අරාවේ පෙර මූලද්‍රව්‍යය.
  3. වම් මූලද්‍රව්‍යය 0 ට සමාන දැයි පරීක්ෂා කර, පසුව divArray [දකුණට] ආපසු එවන්න.
  4. වෙනත් ආකාරයකින් divArray [දකුණේ] සහ divArray [වමේ -1] හි XOR ආපසු එවන්න.

පැහැදිලි කිරීම

විසඳීම සඳහා අපි නිඛිල සංඛ්‍යාවක් සහ විමසුම් කිහිපයක් ලබා දී ඇත. එවිට අපෙන් ඉල්ලා සිටින්නේ ශ්‍රේෂ් greatest තම අමුතු බෙදුම්කරුගේ XOR සොයා ගැනීමටය. විමසුම්වල පූර්ණ සංඛ්‍යා දෙකක් අඩංගු වේ. ඉතින්, එයින් අදහස් වන්නේ එම පූර්ණ සංඛ්‍යා දෙක තුළ අපට පරාසයක් ඇති බවයි. මේ සඳහා, පළමුවෙන්ම, අපි අරාව හරහා ගමන් කරන අතරම, එක් එක් අංකයේ සියලුම බෙදීම් සොයා ගැනීමට යන්නෙමු. එවිට අපි වරකට දී ඇති අරාවකින් අංකය ලබා ගැනීමට යන්නෙමු. අපි විශේෂයෙන් දී ඇති මූලද්‍රව්‍යයක් සඳහා ලූපයක් ආරම්භ කරමු. ලූපය තුළ, අපි වත්මන් මූලද්‍රව්‍යය 2 න් බෙදමින් මූලද්‍රව්‍යය තුළම යාවත්කාලීන කරන්නෙමු. වත්මන් මූලද්රව්යය අමුතු බව සොයා නොගන්නා තෙක් මෙම දෙය දිගටම කරගෙන යනු ඇත. අංකය අමුතු බවට පත්වන කාලය, අපි ලූපයෙන් පිටත කැඩී යයි.

අරාවෙහි සෑම මූලද්‍රව්‍යයකම එක් එක් ගමන් කිරීම සඳහා, ප්‍රති result ලය තල්ලු කරන්න divArray අරාව, එය අමුතු තැනක් බවට පත්වේ. දී ඇති අරාවෙහි ඇති ආකාරයට අරාවෙහි සමාන මූලද්‍රව්‍යයක් පවතිනු ඇත. නමුත් සියලුම බෙදුම්කරුවන් සිටින්නේ ඩිව්ආරේ ​​හි ය. අරාව සම්පූර්ණ කිරීමෙන් පසු, සියලු බෙදුම්කරුවන් ගබඩා කර ඇති අරාව හරහා ගමන් කරන්න. මේ අනුව, සියලු අගයන් ගබඩා කරන divArray අරාව යනු බෙදුම්කරුවන් වේ. එවිට අපි divArray අගයන් මත XOR මෙහෙයුම සිදු කිරීමට යන්නෙමු. අපි divArray හරහා ගමන් කරන්නෙමු, සහ XOR වත්මන් මූලද්‍රව්‍යය සහ අරාවේ පෙර අංගය. වත්මන් හා පෙර අගය ලෙස එක් එක් යුගල මත සිදුකරන මෙහෙයුම සිදු වන තුරු මෙම ක්‍රියාව කළ යුතුය.

ඉතින්, අපට පරාසයක්, වම සහ දකුණ ලෙස විමසුමක් ලබා දුන් විට. එවිට අපි පරීක්ෂා කිරීමට යන්නේ වම් බිංදුවට සමානද යන්නයි. ඉන්පසු divArray [දකුණට] ආපසු යන්න, එසේ නොමැති නම් අපි divArray [දකුණේ] සහ divArray [වමේ -1] හි XOR ආපසු ලබා දෙන්නෙමු.

කේතය

පරාසයේ විශාලතම අමුතු බෙදුම්කරුගේ XOR පිළිබඳ විමසුම් වලට පිළිතුරු දීමට C ++ කේතය

#include<iostream>

using namespace std;

void getDivisorArray(int arr[], int divArray[], int n)
{
    for (int i = 0; i < n; i++)
    {
        while (arr[i] % 2 != 1)
            arr[i] /= 2;

        divArray[i] = arr[i];
    }
    for (int i = 1; i < n; i++)
        divArray[i] = divArray[i - 1] ^ divArray[i];
}

int solveQuery(int divArray[], int left, int right)
{
    if (left == 0)
        return divArray[right];
    else
        return divArray[right] ^ divArray[left - 1];
}

int main()
{
    int arr[] = {2, 6, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    int divArray[n];
    getDivisorArray(arr, divArray, n);

    cout << solveQuery(divArray, 1, 2) << endl;
    cout << solveQuery(divArray, 0, 1) << endl;

    return 0;
}
2
2

පරාසයේ විශාලතම අමුතු බෙදුම්කරුගේ XOR පිළිබඳ විමසීම්වලට පිළිතුරු දීමට ජාවා කේතය

class QueriesXOR
{
    public static void getDivisorArray(int arr[], int divArray[], int n)
    {
        for (int i = 0; i < n; i++)
        {
            while (arr[i] % 2 != 1)
                arr[i] /= 2;

            divArray[i] = arr[i];
        }
        for (int i = 1; i < n; i++)
            divArray[i] = divArray[i - 1] ^ divArray[i];
    }
    
    static int solveQuery(int divArray[], int l, int r)
    {
        if (l == 0)
            return divArray[r];
        else
            return divArray[r] ^ divArray[l - 1];
    }
    
    public static void main (String[] args)
    {
        int arr[] = {2, 6, 4};
        int n = arr.length;

        int divArray[] = new int[n];
        getDivisorArray(arr, divArray, n);

        System.out.println(solveQuery(divArray, 1, 2)) ;
        System.out.println (solveQuery(divArray, 0, 1));
    }
}
2
2

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (එන් ලොග් එන්) එහිදී “එන්” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ. සහ අරාව ලොගයේ ඇති අංක 2 පදනම් XNUMX වේ. ලොග් n සාධකය වන්නේ අප අමුතු බෙදුම්කරුවෙකු ලබා ගන්නා තෙක් සංඛ්‍යා බෙදීමයි.

අභ්‍යවකාශ සංකීර්ණතාව

මත) එහිදී “එන්” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ. අවකාශය ගන්නා xor අගයන් ගබඩා කිරීම සඳහා අපි අරාවක් භාවිතා කර ඇත්තෙමු.