Айрым жуп сандарга ээ эсептөөчү топтомдор


Кыйынчылык деңгээли жеңил
Көп суралган Cisco Expedia Myntra SAP Labs Taxi4Sure
согуштук тизме таштанды Ички топтом

Биз маектешүүдө кандайдыр бир учурда же башка учурда ички көйгөй менен күрөшүп келгенбиз. Маектешкендер бул көйгөйлөрдү да жакшы көрүшөт. Бул көйгөйлөр аларга ар бир студенттин түшүнүгүн жана ой жүгүртүүсүн текшерүүгө жардам берет. Ошентип, мындан ары эч нерсени ойлонбостон, түз эле көйгөйгө секирип кетели.

Бөлүм-1

Проблеманын баяндалышы

Бизге сандардын айкалышы / массиви берилди. Биз уникалдуу жуп сандарга ээ болгон ички топтордун санын жазышыбыз керек.

Бир аз мисал келтирели:

киргизүү:

[1,2,5,6,3,2,1,1,8]

Мүмкүн ички топтомдор:

[2,6]

[6,8]

[2,6,8]

Эскертүү: Бирдей сандары бар ички топтомдор башкача деп эсептелбейт

Мүмкүн болгон жооптордун ички топтомдорунун бирин бөлүп көрсөтүү менен дагы бир мисалды келтирейин.

Айрым жуп сандарга ээ эсептөөчү топтомдор

Бөлүм-2

талдоо

Эмне каалай тургандыгыбызды билүүнүн көптөгөн жолдору бар. The Кара күч мүмкүн болгон бардык ички топтомдорду таап, анда биздин эрежеге жооп бергендерди табуу.

Жогорудагы ыкма башты дубалга ургандан башка эч нерсе эмес. Ошентип, сизди келесоо деп айтуудан уялуумдан кутулуу үчүн, жоопту эң кыска убакытта алууга жардам бере турган эң жөнөкөй ыкмаларды иштеп чыктым.

Жуп санга туш болгон сайын бизде эки тандоо бар

  • Ички топтомдо болууну тандай алат
  • Ички топтомдон тышкары калууну тандашы мүмкүн

Ошентип, азыр биздин алдыбызда турган бирден-бир милдет - бул номердин уникалдуу же өзгөчө эместигин аныктоо. (Жогоруда айтылган эрежеге рахмат)

Келгиле, процессти жокко чыгаралы:

  • Биринчиден, а HashSet биз кездешкен жуп сандарды сактоо үчүн
  • Экинчиден, цикл иштетүү
  • Сандын жуп экендигин текшериңиз
  • Эгерде сан жуп болсо, ага HashSetти кошобуз
  • HashSet өз-өзүнчө буйрутма берип, бизде уникалдуу элементтер гана бар экендигин камсыз кылат
  • Андан кийин HashSetтен элементтердин санын табабыз
  • Бул сан биздеги уникалдуу жуп сандардын санын билдирет
  • Бул санакты колдонуп, андан кийин кичи топтомдордун санын табабыз
  • Ички топтордун саны = 2 ^ эсептөө-1

Жогорудагы процессти төмөндөгүдөй кодго коюуга болот:

Айрым жуп сандарга ээ эсептөөчү топтомдор үчүн Java коду

public class Main
{
    public static int evenSub(int arr[],int n)
    {
        HashSet<Integer>store=new HashSet<Integer>();
        for(int i=0;i<arr.length;i++)
        {
            if(arr[i]%2==0)
                store.add(arr[i]);
        }
        int p=store.size();
        return (int)(Math.pow(2,p)-1);
    }
    public static void main(String[] args)  
    { 
    int arr[] = {2, 1, 9, 2, 6, 5, 3}; 
    int n = arr.length; 
    System.out.println
        ("Number of subsets = "+ evenSub(arr, n)); 
    }
}
2, 1, 9, 2, 6, 5, 3
3

Айрым сандарга ээ эсептөөчү топтомдор үчүн C ++ коду

Javaдан C ++ которулганда, биз HashSetтин ордуна Unordered Setти колдонуп, бир нече параметрлерди өзүбүзгө ылайыктап айлантабыз.

int evenSub(int arr[],int n)
{
    unordered_set<int>store; 
    for(int i=0;i<n;i++)
    {
        if(arr[i]%2==0)
            store.insert(arr[i]);
    }
    int p=store.size();
    return (pow(2,p)-1);
}
int main() 
{
    int arr[] = {
4, 2, 1, 9, 2, 6, 5, 3
7

Айрым жуп сандарга ээ эсептөөчү топтомдордун татаалдыгын талдоо

Убакыт татаалдыгы = O (n)

Космостун татаалдыгы = O (n)

Убакыт татаалдыгы

  • Биз O (n) массивден өтүп бара жатабыз
  • Ички топтомго кошуудан мурун ар бир элементти карап чыгабыз

Космостун татаалдыгы

  • Бул O (n), анткени эң начар учурда биз бүтүндөй массивди сактай алабыз