Check in binary array the number represented by a subarray is odd or even

The problem “Check in binary array the number represented by a subarray is odd or even” states that you are given a binary array and a range. The array consists of the number in the form of 0s and 1s. The problem statement asks to find out the number represented in a subarray in the range [left, right] is even or odd.

Example

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

odd even

Explanation

Left, right = 1,4, so the number will be 1101 which in decimal will be 13 so it is odd.

Left, right = 0,3 which represents the number 1110 which in decimal will be 14 which is even.

Algorithm

1. Check if the array’s right index is 1 or 0.
2. If it is 1, then it is odd, print odd.
3. If it is 0, then it is even, print even.

Explanation

To Check in binary array the number represented by a subarray is odd or even, we are given a binary array. So from the binary array, we mean to say that the number in the array will be in the form of only 0s and 1s. We are given a range that consists of a starting point on the left side and an ending range on the right side. In between this range, we will get a subarray of 0s and 1s. These 0s and 1s combine to form a number which can be easily interpreted as a decimal number.

The same thing we will do with these queries, we are given a range. Since we can represent the binary number as 0 and 1. If we have the last bit of a binary number as a 1, it means the number is odd. The reason being that the first bit of any number will be represented as a decimal number is in the form of 2⁰. So whatever the whole number will be but if the last bit of any binary number is 1. It is going to be odd, and if the last bit of the binary number is 0, the multiplication of 2⁰ with 0, results in 0, so nothing changes in it there.

So in order to solve the check in binary array the number represented by a subarray is odd or even for multiple queries, we will be checking the last bit of the binary number, but we have to check in the sub-array created in the range, so we will be checking the array[right] value if it is equal to 1, then the whole number is going to be odd, else the number will be even.

Code

C++ to check the number represented by a subarray is odd or even

#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 code to check the number represented by a subarray is odd or even

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

Complexity Analysis

Time Complexity

O(q) where “q” is the number of queries we have to perform. Because each query can be answered in O(1) time complexity.

Space Complexity

O(1) as no extra space is required. Thus space complexity of Check in binary array the number represented by a subarray is odd or even problem is constant.