C++에서 다른 배열의 요소로 나눌 수 없는 배열의 요소

이 문제에서는 두 개의 배열 arr1[]과 arr2[]가 제공됩니다. 우리의 임무는 다른 배열의 어떤 요소로도 나눌 수 없는 배열의 요소를 찾는 프로그램을 만드는 것입니다.

문제 설명: 여기서 우리는 rr2의 어떤 요소로도 나눌 수 없는 arr1의 모든 요소를 ​​찾아야 합니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력: arr1[] ={17, 15, 5, 12, 8} arr2[] ={5, 4}

출력: 17

설명 -

arr1의 요소와 이를 나누는 요소,

17 -> 어떤 요소도 그것을 나눌 수 없습니다.
15 -> 5는 요소를 나눕니다.
5 -> 5는 요소를 나눕니다.

12 -> 4는 요소를 나눕니다.

8 -> 4는 요소를 나눕니다.

해결 방법 -

문제를 해결하는 간단하고 순진한 접근 방식은 직접 방법을 사용하는 것입니다. 우리는 arr1을 반복하고 arr1의 각 요소에 대해 arr2의 요소가 요소를 나누는지 확인합니다. 분할하는 요소가 없으면 요소를 인쇄합니다.

알고리즘 -

1단계: arr1에 대한 루프, i -> 0 ~ n-1.

2.1단계: 각 arr1[i]에 대해 루프 arr2, j -> 0에서 n-1까지.

2.2.1단계: arr1[i] % arr2[j] ==0이면 계속 플래그 =-1입니다.

2.3단계: 플래그 !=-1이면 arr1[i]을 인쇄합니다.

우리 솔루션의 작동을 설명하는 프로그램,

예시

#include<iostream>
using namespace std;

void findEleNotDivisbleByArray(int arr1[], int arr2[], int arr1Size, int arr2Size) {
   
   int flag = 0;
   for (int i = 0; i < arr1Size; i++) {
      flag = 0;
      for (int j = 0; j < arr2Size; j++){
         
         if( arr1[i] % arr2[j] == 0 ) {
            flag = -1;   
            break;
         }
      }
      if ( flag == 0 )
            cout<<arr1[i]<<"\t";
   }
}

int main()
{
   int arr1[] = {17, 15, 5, 12, 23, 8};
   int arr2[] = {5, 4};
   int arr1Size = sizeof(arr1)/sizeof(arr1[0]);
   int arr2Size = sizeof(arr2)/sizeof(arr2[0]);
   cout<<"Elements of an array that are not divisible by any element of another array are ";
   findEleNotDivisbleByArray(arr1, arr2, arr1Size, arr2Size);
   return 0;
}

출력 -

Elements of an array that are not divisible by any element of another array are 17 23

이 솔루션은 유효하지만 효율적이지 않습니다. 따라서 문제에 대한 효율적인 솔루션을 살펴보겠습니다.

이 방법에서는 arr1 요소의 배열 isDivisible[]을 생성합니다. arr2의 모든 요소에 대해 arr1의 가장 큰 요소까지 모든 배수를 표시합니다. 그리고 isDisible 배열에서 false로 표시된 모든 요소를 ​​인쇄하십시오.

우리 솔루션의 작동을 설명하는 프로그램,

예시

#include<iostream>
using namespace std;

void findEleNotDivisbleByArray(int arr1[], int arr2[], int arr1Size, int arr2Size) {
   
   int maxEle = 0;
   for (int i = 0; i < arr1Size; i++)
      if (arr1[i] > maxEle)
         maxEle = arr1[i];

   int mark[maxEle];
   for (int i = 0; i < arr2Size; i++)
      for (int j = arr2[i]; j <= maxEle; j += arr2[i])
         mark[j] = 1;
   for (int i = 0; i < arr1Size; i++)
      if ( mark[arr1[i]] != 1)
         cout << arr1[i] << endl;
}

int main()
{
   int arr1[] = {17, 15, 5, 12, 8};
   int arr2[] = {5, 4};
   int arr1Size = sizeof(arr1)/sizeof(arr1[0]);
   int arr2Size = sizeof(arr2)/sizeof(arr2[0]);
   cout<<"Elements of an array that are not divisible by any element of another array are ";
   findEleNotDivisbleByArray(arr1, arr2, arr1Size, arr2Size);
   return 0;
}

출력 -

Elements of an array that are not divisible by any element of another array are 17