Хоёртын массивыг шалгахдаа дэд массиваар илэрхийлсэн тоо нь сондгой эсвэл тэгш байна


Хэцүү байдлын түвшин Easy
Байнга асуудаг Cisco Fab IBM Microsoft- PayU Snapchat Snapdeal Teradata
Array Бит

“Дэд массиваар дүрслэгдсэн тоо нь сондгой эсвэл тэгш байна” гэсэн хоёрдогч массивыг шалгахад танд хоёртын массив ба муж өгөгдсөн болохыг зааж өгсөн болно. Массив нь 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

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (q) хаана "Q" гэдэг нь бидний хийх ёстой асуулгын тоо юм. Асуулт бүрийг O (1) цагийн төвөгтэй байдлаар хариулж болох тул.

Сансрын нарийн төвөгтэй байдал

O (1) нэмэлт зай шаардагдахгүй тул. Тиймээс хоёртын массив дахь Check-ийн орон зайн нарийн төвөгтэй байдал нь дэд массиваар дүрслэгдсэн тоо нь сондгой эсвэл тэгш тоо тогтмол байна.