ලීට්කෝඩ් විසඳුමක බලය  


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ Apple ජංගම දුරකථන
ඇල්ගොරිතම බිට් හැසිරවීම බිටු කේතීකරණය සම්මුඛ පරීක්ෂණ සම්මුඛ සාකච්ඡා ලීට්කෝඩ් LeetCodeSolutions ගණිතය

අපට ලබා දී ඇත්තේ අ නිඛිල ඉලක්කය වන්නේ පූර්ණ සංඛ්‍යාව දෙකක බලයක් ද යන්න පරීක්ෂා කිරීමයි, එනම් එය කිසියම් සමස්ත බලයක් ලෙස නිරූපණය කළ හැකිය.2'.

ලීට්කෝඩ් විසඳුම් දෙකක බලයපින්

උදාහරණයක්  

16
Yes
13
No

ප්රවේශය  

සුළු විසඳුමක් විය හැකිය: නිඛිලයේ සියලු ප්‍රධාන සාධක සියල්ලම තිබේදැයි පරීක්ෂා කරන්න '2'. මෙම ක්‍රමයේ කාල සංකීර්ණතාව O (log2N). එය ප්‍රශස්ත ආකාරයකින් සිදු කිරීම සඳහා, අපට බිට් හැසිරවීම් සඳහා සහාය ලබා ගත හැකිය.

“දෙකක බලයක් ඇති ඕනෑම අංකයකට ද්විමය නිරූපණයෙන් එක් බිට් කට්ටලයක් පමණක් තිබිය හැකිය”

එය පමණක් ඇති බව පරීක්ෂා කරන්නේ කෙසේද? තනි බිට් කට්ටලය ද්විමය ස්වරූපයෙන්?

ඕනෑම අංකයක් සලකා බලන්න, x.

දැන්, x යනු දෙකක බලයක් නම්, එසේ නම් (x - 1) සියල්ල අක්‍රිය කරයි දකුණු බිටු සෙට් බිට් වෙත (ඒවා '0' ලෙස සකසන්න) සහ සෙට් බිට් සැකසෙන්නේ නැත.

x = 8 [1000], x - 1 = 7 [0111]

එබැවින්, භාවිතා කිරීම බිට්විස් සහ x සහ (x - 1) හි, සංඛ්‍යා දෙකක බලයක් නම් අපට කිව හැකිය, එසේ නම්, x & (x - 1) = 0

ඇල්ගොරිතම (සුළු)  

  1. අංකය බෙදීම දිගටම කරගෙන යන්න '2' එය බෙදීමට නොහැකි වන තෙක් '2' තවදුරටත්.
  2. අංකය සමාන නම් '1':
    • නිඛිලය යනු දෙකක බලයකි
  3. එසේ නැතහොත්
    • නිඛිලය දෙකක බලයක් නොවේ
මෙයද බලන්න
ලීට්කෝඩ් විසඳුමේ බලය

ඇල්ගොරිතම (බිට්-හැසිරවීම)  

  1. X & (x - 1) බිංදුවට සමාන දැයි පරීක්ෂා කරන්න
    • ඔව් නම්, අංකය 2 ක බලයකි
    • නිඛිලය 2 ක බලයක් නොවේ

ක්රියාත්මක කිරීම  

සී ++ ලීට්කෝඩ් විසඳුමක බලය පිළිබඳ වැඩසටහන

බොළඳ ක්‍රමය

#include <bits/stdc++.h>
using namespace std;

bool powerOfTwo(int n)
{
    while(n % 2 == 0)
        n /= 2;
    return (n == 1);
}


int main()
{
    int n = 16;
    if(powerOfTwo(n))
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';


    return 0;
}

ප්‍රශස්ත ක්‍රමය

#include <bits/stdc++.h>
using namespace std;

bool powerOfTwo(int n)
{
    //16 = [10000]
    //15 = [01111]
    //16 & 15 = 0
    return (n & (n - 1)) == 0;
}


int main()
{
    int n = 16;
    if(powerOfTwo(n))
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';


    return 0;
}
Yes

ලීට්කෝඩ් විසඳුමක බලය පිළිබඳ ජාවා වැඩසටහන

බොළඳ ක්‍රමය

class power_of_two
{
    public static boolean powerOfTwo(int n)
    {
        while(n % 2 == 0)
            n /= 2;
        return (n == 1);
    }

    public static void main(String args[])
    {
        int n = 16;
        if(powerOfTwo(n))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

ප්‍රශස්ත ක්‍රමය

class power_of_two
{
    public static boolean powerOfTwo(int n)
    {
        return (n & (n - 1)) == 0;
    }

    public static void main(String args[])
    {
        int n = 16;
        if(powerOfTwo(n))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
Yes

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

ලීට්කෝඩ් විසඳුමක බලයේ කාල සංකීර්ණත්වය

නයිව් ප්‍රවේශයේ කාල සංකීර්ණත්වය O (log2N), එහිදී N = දී ඇති පූර්ණ සංඛ්‍යාවක්. කෙසේ වෙතත්, ප්‍රශස්ත ප්‍රවේශය වේගවත් වන අතර, බිට්වේස්-ඇන්ඩ් වේගවත් වන අතර එම නිසා කාල සංකීර්ණතාවයක් ඇත ඕ (1).

ලීට්කෝඩ් විසඳුමක බලයේ අභ්‍යවකාශ සංකීර්ණතාව

වැඩසටහනේ භාවිතා වන අවකාශය පමණක් ශ්‍රිත අත්සන වේ. එබැවින් නියත අවකාශය භාවිතා වේ - ඕ (1).