Ստուգեք երկուական զանգվածում ենթանկարի միջոցով ներկայացված թիվը կենտ կամ զույգ է


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Cisco Ֆաբ IBM Microsoft PayU Snapchat Snapdeal Տերադատա
Դասավորություն Բիթեր

«Ստուգեք երկուական զանգվածում ենթածրագրի կողմից ներկայացված թիվը կենտ կամ զույգ է» խնդիրը նշում է, որ ձեզ տրվում է երկուական զանգված և տիրույթ: Rayանգվածը բաղկացած է թվից `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, որը զույգ է:

Ստուգեք երկուական զանգվածում ենթանկարի միջոցով ներկայացված թիվը կենտ կամ զույգ է

 

Ալգորիթմ

  1. Ստուգեք, արդյոք զանգվածի աջ ինդեքսը 1 է կամ 0:
  2. Եթե ​​1 է, ուրեմն տարօրինակ է, տպիր տարօրինակ:
  3. Եթե ​​0 է, ուրեմն հավասար է, տպիր հավասար:

բացատրություն

Երկուական զանգվածում ստուգելու համար ենթաշարայնով ներկայացված թիվը կենտ է կամ զույգ, մեզ տրվում է երկուական դասավորություն, Այսպիսով, երկուական զանգվածից մենք ուզում ենք ասել, որ զանգվածում համարը կլինի ընդամենը 0-ի և 1-ի տեսքով: Մեզ տրված է մի շարք, որը բաղկացած է ձախ կողմի մեկնակետից և աջ կողմում ավարտվող տիրույթից: Այս միջակայքի միջև մենք կստանանք 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

Բարդության վերլուծություն

Timeամանակի բարդություն

Ո (ք) որտեղ "Q" հարցումների քանակն է, որը մենք պետք է կատարենք: Քանի որ յուրաքանչյուր հարցում կարող է պատասխանվել O (1) ժամանակի բարդությամբ:

Տիեզերական բարդություն

Ո (1) քանի որ լրացուցիչ տարածք չի պահանջվում: Այսպիսով, Ստուգեք երկուական զանգվածի տիեզերական բարդությունը, ենթախմբով ներկայացված թիվը տարօրինակ է կամ էլ խնդիրը հաստատուն է: