이진 배열에서 하위 배열로 표시된 숫자가 홀수 또는 짝수인지 확인하십시오.  


난이도 쉽게
자주 묻는 질문 시스코 IBM Microsoft 알레그로 Snapchat 스냅 딜 테라 데이타
배열 비트

"이진 배열에서 하위 배열이 나타내는 숫자가 홀수 또는 짝수인지 확인"문제는 이진 배열과 범위가 주어 졌다는 것을 나타냅니다. 배열은 0과 1 형식의 숫자로 구성됩니다. 문제 설명은 [left, right] 범위에서 하위 배열에 표시된 숫자가 짝수 또는 홀수인지 확인하도록 요청합니다.

예  

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

설명

왼쪽, 오른쪽 = 1,4이므로 숫자는 1101이되고 십진수로 13이되어 홀수입니다.

Left, right = 0,3은 1110 진수로 14가되는 숫자 XNUMX을 나타냅니다.

이진 배열에서 하위 배열로 표시된 숫자가 홀수 또는 짝수인지 확인하십시오.

 

암호알고리즘  

  1. 배열의 오른쪽 인덱스가 1 또는 0인지 확인하십시오.
  2. 1이면 홀수이고 홀수로 인쇄합니다.
  3. 0이면 짝수이고 짝수 인쇄입니다.

설명  

이진 배열을 확인하기 위해 부분 배열이 나타내는 숫자가 홀수이거나 짝수입니다. 정렬. 따라서 이진 배열에서 배열의 숫자는 0과 1의 형태로만 나타납니다. 왼쪽의 시작점과 오른쪽의 끝 범위로 구성된 범위가 제공됩니다. 이 범위 사이에서 0과 1의 하위 배열을 얻습니다. 이러한 0과 1이 결합되어 십진수로 쉽게 해석 할 수있는 숫자를 형성합니다.

참조
문자열 훌륭한 Leetcode 솔루션 만들기

이러한 쿼리로 수행 할 동일한 작업에 범위가 제공됩니다. 이진수를 0과 1로 나타낼 수 있기 때문에 이진수의 마지막 비트가 1이면 그 숫자가 홀수임을 의미합니다. 숫자의 첫 번째 비트가 2 진수로 표시되는 이유는 XNUMX의 형식입니다.. 따라서 정수가 무엇이든지간에 이진수의 마지막 비트가 1이면 홀수이고 이진수의 마지막 비트가 0이면 2의 곱셈이됩니다.0 0을 사용하면 0이되므로 아무것도 변경되지 않습니다.

따라서 이진 배열의 검사를 해결하기 위해 하위 배열이 나타내는 숫자가 홀수이거나 여러 쿼리에 대해 짝수입니다. 이진수의 마지막 비트를 검사하지만 범위에서 생성 된 하위 배열을 검사해야합니다. , 그래서 우리는 그것이 1이면 array [right] 값을 검사 할 것입니다. 그러면 정수는 홀수가 될 것이고 그렇지 않으면 숫자는 짝수 일 것입니다.

암호  

하위 배열로 표시된 숫자가 홀수인지 짝수인지 확인하는 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) 추가 공간이 필요하지 않습니다. 따라서 이진 배열에서 검사의 공간 복잡도는 하위 배열로 표시되는 숫자가 홀수이거나 문제가 일정합니다.