Екілік массивке қосалқы массивпен берілген сан тақ немесе жұп болған жағдайда жазыңыз


Күрделілік дәрежесі оңай
Жиі кіреді Cisco Фаб IBM Microsoft PayU Snapchat Шапшаң Терадата
Array Биттер

«Қосарлы массивті тексеру кіші массивпен берілген нөмір тақ немесе жұп» деген есеп сізге екілік массив пен диапазон берілгенін айтады. Массив 0s және 1s түріндегі саннан тұрады. Проблемалық есеп [солға, оңға] диапазонында субаррада көрсетілген санның жұп немесе тақ екенін анықтауды сұрайды.

мысал

arr[] = {1,1,1,0,1}
Left, right = 1, 4
Left, right = 0, 3
odd even

Түсіндіру

Солға, оңға = 1,4, сондықтан 1101 болады, ондық бөлшек 13-ке тең болады, сондықтан тақ болады.

Солға, оңға = 0,3, бұл 1110 санын білдіреді, ондық таңбада 14 тең болады, ал ол жұп болады.

Екілік массивке қосалқы массивпен берілген сан тақ немесе жұп болған жағдайда жазыңыз

 

Алгоритм

  1. Массивтің оң индексі 1 немесе 0 екенін тексеріңіз.
  2. Егер ол 1 болса, онда тақ, тақ тақ.
  3. Егер ол 0-ге тең болса, онда ол жұп, тіпті басылады.

Түсіндіру

Екілік массивті тексеру үшін ішкі массив ұсынған сан тақ немесе жұп болып табылады, бізге екілік берілген массив. Сонымен, екілік массивтен жиымдағы сан тек 0s және 1s түрінде болады деп айтқымыз келеді. Бізге сол жақтағы бастапқы нүктеден және оң жақтағы аяқталатын диапазоннан тұратын диапазон беріледі. Осы аралықта біз 0 және 1 секцияларының қосымшасын аламыз. Бұл 0 мен 1 сандары біріктіріліп, ондық сан ретінде оңай түсіндірілетін санды құрайды.

Осы сұраулармен бірдей жұмыс жасайтын боламыз, бізге ауқым беріледі. Біз екілік санды 0 және 1 түрінде көрсете алатындықтан, егер екілік санның соңғы биті 1-ге тең болса, бұл санның тақ екенін білдіреді. Себебі кез-келген санның бірінші биті ондық сан түрінде ұсынылатын болады, бұл 2 түрінде болады0. Сонымен, бүтін сан қандай болмақ, бірақ кез-келген екілік санның соңғы биті 1-ге тең болса, тақ болады, ал егер екілік санның соңғы биті 0-ге тең болса, 2-ге көбейту0 0-мен 0 нәтижесі шығады, сондықтан онда ештеңе өзгермейді.

Сонымен, екілік массивтегі тексеруді шешу үшін ішкі массив ұсынған сан тақ немесе жұп сұранысқа ие болса, біз екілік санның соңғы битін тексереміз, бірақ диапазонда құрылған ішкі массивті тексеруіміз керек , сондықтан [оң] жиымының мәні 1-ге тең болғанын тексереміз, сонда бүкіл сан тақ болады, әйтпесе сан жұп болады.

код

Ішкі массивпен берілген санды тақ немесе жұп етіп тексеру үшін C ++

#include<iostream>

using namespace std;

void IsEvenOrOdd (int arr[], int n, int left, int right)
{
    if (arr[right] == 1)
        cout << "odd" << endl;
    else
        cout << "even" << endl;
}
int main()
{
    int arr[] = {1,1,1,0,1};
    int n = sizeof(arr)/sizeof(arr[0]);
    IsEvenOrOdd (arr, n, 1, 4);
    IsEvenOrOdd (arr, n, 0, 3);
    return 0;
}
odd
even

Ішкі массивпен көрсетілген нөмірді тексеруге арналған Java коды тақ немесе жұп

class BinaryOddEven
{
    static void IsEvenOrOdd (int arr[], int n, int left, int right)
    {
        if (arr[right] == 1)
            System.out.println( "odd") ;
        else
            System.out.println ( "even") ;
    }
    public static void main (String[] args)
    {
        int arr[] = {1,1,1,0,1};
        int n = arr.length;
        IsEvenOrOdd (arr, n, 1, 4);
        IsEvenOrOdd (arr, n, 0, 3);

    }
}
odd
even

Күрделілікті талдау

Уақыттың күрделілігі

O (q) қайда «Q» - біз орындайтын сұраулар саны. Себебі әр сұраққа O (1) уақыт күрделілігінде жауап беруге болады.

Ғарыштың күрделілігі

O (1) өйткені қосымша орын қажет емес. Осылайша, екілік массивтегі Check-тің кеңістігі ішкі массивпен берілген сан тақ немесе жұп мәселе тұрақты болады.