C++에서 조건부 연산자를 사용하지 않고 배열에서 가장 큰 요소 찾기

일부 요소가 있는 배열 A가 있다고 가정합니다. 배열 A에서 가장 큰 요소를 찾아야 하지만 제약 조건은 조건 연산자를 사용할 수 없다는 것입니다. 따라서 A =[12, 63, 32, 24, 78, 56, 20]이면 최대 요소는 78이 됩니다.

이 문제를 해결하기 위해 비트 AND 연산을 사용합니다. 처음에는 배열에 하나의 추가 요소 INT_MAX(모든 비트가 1인 경우)를 삽입합니다. 그런 다음 배열에서 모든 쌍의 최대 AND 값을 찾으려고 합니다. 이렇게 얻은 최대값에는 INT_MAX의 AND 값과 원래 배열의 가장 큰 요소가 포함되며 이것이 결과입니다.

예시

#include <iostream>
#include <vector>
using namespace std;
int checkBit(int pattern, vector<int> arr, int n) {
   int count = 0;
   for (int i = 0; i < n; i++)
      if ((pattern & arr[i]) == pattern)
         count++;
   return count;
   }
   int findLargestElement(int arr[], int n) {
      vector<int> elements_vector(arr, arr + n);
      elements_vector.push_back(INT_MAX);
      n++;
      int res = 0;
      for (int bit = 31; bit >= 0; bit--) {
         int count = checkBit(res | (1 << bit), elements_vector, n);
         if ((count | 1) != 1)
               res |= (1 << bit);
      }
      return res;
}
int main() {
   int arr[] = {12, 63, 32, 24, 78, 56, 20};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Largest element is: " << findLargestElement(arr, n);
}

출력

Largest element is: 78