C++の別の配列の要素で割り切れない配列の要素

この問題では、2つの配列arr1[]とarr2[]が与えられます。私たちのタスクは、別の配列のどの要素でも割り切れない配列の要素を見つけるプログラムを作成することです。

問題の説明： ここでは、arr2のどの要素でも割り切れない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