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

Difficulty Level Easy
Frequently asked in Cisco Fab IBM Microsoft PayU Snapchat Snapdeal Teradata
Array Bits

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.

Please click Like if you loved this article?

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

 

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.

See also
Make The String Great Leetcode Solution

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 20 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.

See also
Find the Duplicate Element

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.

Please click Like if you loved this article?

Please click Like if you loved this article?

Ads Blocker Image Powered by Code Help Pro
Ads Blocker Detected!!!

This website does not work properly with AdBlock. We have detected that you are using extensions to block ads. Please disable Adblocker to view the content.

Refresh