Праверце ў двайковым масіве лік, прадстаўлены падмасівам, няцотны і цотны  


Узровень складанасці Лёгка
Часта пытаюцца ў Cisco Fab IBM Microsoft PayU Snapchat Snapdeal Teradata
масіў біты

Праблема «Праверыць у двайковым масіве лік, прадстаўлены падмасівам, няцотны і цотны» абвяшчае, што вам дадзены двайковы масіў і дыяпазон. Масіў складаецца з ліку ў выглядзе 0 і 1. Пастаноўка праблемы патрабуе высветліць лік, прадстаўлены ў падмасіве ў дыяпазоне [злева, справа], цотны альбо няцотны.

Прыклад  

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

Тлумачэнне

Злева, справа = 1,4, таму лік будзе 1101, што ў дзесятковай лічбе будзе 13, таму гэта няцотна.

Злева, справа = 0,3, якое ўяўляе лік 1110, дзе ў дзесятковай лічбе будзе 14, што цотны.

Праверце ў двайковым масіве лік, прадстаўлены падмасівам, няцотны і цотныPin

 

Алгарытм  

  1. Праверце, ці правільны індэкс масіва роўны 1 ці 0.
  2. Калі роўна 1, значыць, няцотная, друкуйце няцотная.
  3. Калі ён роўны 0, значыць, ён цотны, надрукуйце цотны.

Тлумачэнне  

Каб праверыць у двайковым масіве, лік, прадстаўлены падмасівам, няцотны і цотны, нам даецца двайковы масіў. Такім чынам, з двайковага масіва мы маем на ўвазе сказаць, што лік у масіве будзе мець форму толькі 0 і 1. Нам дадзены дыяпазон, які складаецца з пачатковай кропкі з левага боку і канчатковай дыяпазону з правага боку. Паміж гэтым дыяпазонам мы атрымаем падмасіў 0 і 1. Гэтыя нумары і адзінкі аб'ядноўваюцца, утвараючы лік, якое можна лёгка інтэрпрэтаваць як дзесятковы лік.

Глядзіце таксама
Зрабіце String выдатным рашэннем Leetcode

Тое ж, што мы будзем рабіць з гэтымі запытамі, нам даецца дыяпазон. Паколькі мы можам прадставіць двайковы лік як 0 і 1. Калі мы маем апошні біт двайковага ліку як 1, гэта азначае, што лік няцотны. Прычына ў тым, што першы біт любога ліку будзе прадстаўлены ў выглядзе дзесятковага ліку ў выглядзе 2. Такім чынам, якім бы ні быў цэлы лік, але калі апошні біт любога двайковага ліку роўны 1. Гэта будзе няцотным, а калі апошні біт двайковага ліку роўны 0, множанне 20 з 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 у двайковым масіве лік, прадстаўлены падмасівам, няцотны ці нават праблема сталая.