چار ليٽ ڪوڊ حل جي طاقت


تڪليف جي سطح آسان
بار بار پڇڻ ۾ ٻه سگا
بٽ مينپوليشن Math

مسئلي جو بيان

اسان کي انٽيگر ڏنو ويو ۽ اسان کي چڪاس ڪرڻو پوندو ته نمبر 4 جي طاقت آهي يا نه. هڪ عدد 4 جي طاقت آهي جيڪڏهن اتي ڪو عدد موجود هجي a اهڙو ،  نمبر = 4 ^ هڪ.

مثال

16
true
5
false

پهچ 1 (بروٽ فورس)

چيڪ ڪرڻ لاءِ هڪ واضح طريقو اهو آهي ته هڪ نمبر 4 جي طاقت آهي يا نه ، اهو آهي 4 جي سڀني فيصلن کي بار بار نمبرن کي ورهائي 4 کي ختم ڪرڻ تائين ته ان کي 4 تائين ورهايو وڃي ۽ آخر ۾ چيڪ ڪريو ته باقي نمبر 1 جي برابر يا نه برابر آهي. جيڪڏهن اهو 1 آهي ته پوءِ اهو واضع آهي ته 4 کان سواءِ ڪو ٻيو عنصر ناهي ، تنهن ڪري نمبر 4 جي طاقت هئي جيڪڏهن اها 1 نه آهي ته نمبر 4 جي طاقت نه آهي.

چار ليٽ ڪوڊ حل جي طاقت لاءِ عمل درآمد

سي ++ پروگرام

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

bool isPowerOfFour(int n) 
{
     if (n == 0) return false;

     while (n % 4 == 0) n /= 4;

     if(n==1) return true;
     else return false;
}

int main() 
{
   int n=16;
    
   if(isPowerOfFour(16)) cout<<"true"<<endl;
   else cout<<"false"<<endl;

   return 0; 
}
true

جاوا پروگرام

import java.util.*;
class Rextester{
    
   public static boolean isPowerOfFour(int n) 
   {     
         if (n == 0) return false;
        
         while (n % 4 == 0) n /= 4;
         
         if(n==1) return true;
         else return false;
        
    }
    
    public static void main(String args[])
    {
       	int n=16;
        System.out.println(isPowerOfFour(n));
    }
}
true

چار ليٽ ڪوڊ حل جي طاقت لاءِ پيچيدگي وارو تجزيو

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

اي [لاگ اين] اسين هر دفعي ڏنل نمبر 4 کان جدا ڪري رهيا آهيون. تنهن ڪري بدترين صورت ۾ لوپ لاگ ان هلندو (بنياد 4) دفعا. ان ڪري اسان چئي سگھون ٿا وقت جي پيچيدگي O (logN) آهي.

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

اي (1): وڌيڪ يادگيري استعمال نه ٿيندي آهي.

پهچ 2 (تعصب)

اسان اڻون ٿا ته حدن ۾ تمام محدود تعداد موجود هوندي (32-bit) حد جيڪا 4 جي طاقت آهي. ڪيئن؟
ڏسو

اسان کي انٽيگر x ڏنو ويو آهي ، تنهن ڪري: x <= 2 ^ 31-1
تنهنڪري هن حد ۾ 4 جي وڌ کان وڌ طاقت هوندي: log4 (2 ^ 31-1) = 15

ھاڻي اسان آساني سان ڪري سگھوٿا 15 نمبر محفوظ ڪري سگھو ٿا.
ان ڪري اسين ھاڻي ھر وقت لاءِ ھر وقت لاءِ ڳولي سگھون ٿا ته اھو 4 جي طاقت آھي يا نھ.

چار ليٽ ڪوڊ حل جي طاقت لاءِ عمل درآمد

سي ++ پروگرام

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

set<int> nums;

bool isPowerOfFour(int n) 
{
    return nums.count(n);
}

int main() 
{
    int n=15;
    int x = 1;
    nums.insert(x);
    for (int i = 1; i < n + 1; ++i) 
    {
      x = x * 4;
      nums.insert(x);
    }
    
   if(isPowerOfFour(16)) cout<<"true"<<endl;
   else cout<<"false"<<endl;

   return 0; 
}
true

جاوا پروگرام

import java.util.*;
class Rextester{
    
    static int n = 15;
    static List<Integer> nums = new ArrayList<Integer>();
    static{
            int x = 1;
            nums.add(x);
            for (int i = 1; i < n + 1; ++i) 
            {
              x = x * 4;
              nums.add(x);
            }
    }
    
    public static boolean isPowerOfFour(int n) 
    {
         return nums.contains(n);
    }
    
    public static void main(String args[])
    {
       	int n=16;
       System.out.println(isPowerOfFour(n));
    }
}
true

چار ليٽ ڪوڊ حل جي طاقت لاءِ پيچيدگي وارو تجزيو

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

اي (1): اسان جا سڀ نمبر آھن جيڪي اسان جي پروگرام ۾ 4 ذخيرو ٿيل طاقت آھن. انهي ڪري اسان هڪ ڏنل نمبر جي ڳولا ڪري سگهون ٿا ۽ مستقل وقت ۾ صحيح يا غلط جي واپسي ڪريون.

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

اي (1): 32 بٽ انٽيگر ان پٽ لاءِ ميموري ۾ صرف 15 نمبر ذخيرا ٿيل آهن يعني مسلسل جڳهه يا اي (1).

پهچ 3بٽ واري سهاري)

بِرٽ پِليشن استعمال ڪندي اسان وڏي مشڪل سان اھو مسئلو حل ڪري سگھون ٿا.
اسان هڪ نمبر لاءِ 4اڻون ٿا 2 جي طاقت لاءِ ، اهو پڻ 2 جي طاقت هجڻ جي ضرورت آهي. اسان اڳ ۾ ئي نمبر جي حالت تي بحث ڪيو آهي XNUMX جي طاقت ٻه ليٽ ڪوڊ حل جي طاقت بئري لپيلي استعمال ڪندي.

سو اچو ته پهرين چڪاس ڪيون ته نمبر ٻن جي طاقت آهي: x> 0 ۽ x & (x - 1) == 0.
هاڻي اسان اهو تجزيو ڪري سگھون ٿا ته جيڪڏهن نمبر 2 جي طاقت به آهي ته اها 4 جي طاقت هوندي ، ۽ جيڪڏهن نمبر 2 جي ايڏي طاقت آهي ته پوءِ اهو 4 جي طاقت نه هوندو.
بائنري نمائندگي ۾ اهو نمبر برابر فقط 1-بٽ ايستائين (4 جي طاقت) يا انوڊ پوزيشن (4 جي طاقت نه) تي مشتمل هوندو.

چار ليٽ ڪوڊ حل جي طاقت

انهي ڪري جيڪڏهن اسان نمبر تي ۽ نمبر سان (4 جي طاقت) نمبر (101010… .10) (بي بنياد 2) نتيجو صفر هوندو.
اسان مٿي ڏنل تصور کي هيڪسڊيڪل ۾ سيڪنڊ نمبر لکندي طور لاڳو ڪري سگھون ٿا (الف 16) (بي بنياد XNUMX).

چار ليٽ ڪوڊ حل جي طاقت لاءِ عمل درآمد

سي ++ پروگرام

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

bool isPowerOfFour(int n) 
{
    return (n > 0)  &&  ((n & (n-1)) == 0)  && ((n & 0xaaaaaaaa) == 0) ;
}

int main() 
{
   if(isPowerOfFour(16)) cout<<"true"<<endl;
   else cout<<"false"<<endl;

   return 0; 
}
true

جاوا پروگرام

import java.util.*;
class Rextester{
    
    public static boolean isPowerOfFour(int n) 
    {
        return (n > 0)  &&  ((n & (n-1)) == 0)  && ((n & 0xaaaaaaaa) == 0) ;
    }
    
    public static void main(String args[])
    {
       	int n=16;
       System.out.println(isPowerOfFour(n));
    }
}
true

چار ليٽ ڪوڊ حل جي طاقت لاءِ پيچيدگي وارو تجزيو

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

اي (1): بيٽسمين ۽ هڪ مسلسل آپريشن آهي.

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

اي (1): مسلسل جاءِ.

پهچ 4 (بٽ مينپوليشن + رياضي)

اسان thatاڻون ٿا ته جيڪڏهن ڪو نمبر 4 جي طاقت آهي ته پوءِ اهو به 2 جي طاقت هوندي. x = 2 ^ a لاءِ ٻنهي صورتن کي غور ڪندي:
هڪ = 2k يا هڪ = 2k + 1

جيڪڏهن اسان هنن 3 نمبرن کي XNUMX تائين ورهايو ته اسان هيٺين طور تي هنيا وينداسين.
2 ^ 2k mod 3 = 4 ^ k mod 3 = (3 + 1) ^ k mod 3 = 1
2 ^ (2k + 1) mod 3 = 2 × 4 ^ k mod 3 = 2 × (3 + 1) ^ k mod 3 = 2

انهيء ڪري 4 جي طاقت هجڻ لاءِ هڪ نمبر جي آخري حالت هئڻ گهرجي:

x 2 جي طاقت آهي ۽ x٪ 3 == 1

چار ليٽ ڪوڊ حل جي طاقت لاءِ عمل درآمد

سي ++ پروگرام

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

bool isPowerOfFour(int n) 
{
     return (n > 0) && ((n & (n-1)) == 0) && ((n % 3) == 1) ;
}

int main() 
{
   if(isPowerOfFour(16)) cout<<"true"<<endl;
   else cout<<"false"<<endl;

   return 0; 
}
true

جاوا پروگرام

import java.util.*;
class Rextester{
    
    public static boolean isPowerOfFour(int n) 
    {
        return (n > 0) && ((n & (n-1)) == 0) && ((n % 3) == 1) ;
    }
    
    public static void main(String args[])
    {
       	int n=16;
       System.out.println(isPowerOfFour(n));
    }
}
true

چار ليٽ ڪوڊ حل جي طاقت لاءِ پيچيدگي وارو تجزيو

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

اي (1): مسلسل وقت.

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

اي (1): مسلسل جاءِ.