C++의 모든 배열 요소로 나눌 수 있는 범위의 숫자 세기

<시간/>

숫자 범위를 정의하기 위해 두 개의 숫자 START와 END가 제공됩니다. 또한 양수 Arr[]의 배열입니다. 목표는 Arr[]의 모든 요소로 나눌 수 있고 [START,END] 범위에 있는 모든 숫자를 찾는 것입니다.

방법 1(순진한 접근)

START에서 END까지 숫자를 탐색하여 이를 수행하고 각 숫자에 대해 숫자가 배열의 모든 요소로 나눌 수 있는지 확인합니다. 예인 경우 카운트를 증가시킵니다.

방법 2(배열 요소의 LCM으로 분할 가능성 확인)

모든 배열 요소의 LCM을 찾은 다음 해당 LCM으로 완전히 나눌 수 있는 [START,END] 범위의 모든 숫자를 확인하고 계산합니다.

예를 들어 이해합시다.

입력

START=1 END=20 Arr[]= { 2, 4, 8 }

출력

Numbers that are divisible by all array elements: 2

설명

Numbers 8 and 16 are in the range that are divisible by all array elements.

입력

START=100 END=200 Arr[]= { 230, 321, 490, 521 }

출력

Numbers that are divisible by all array elements: 0

설명

No number between 100 to 200 divisible by any array element.

방법 1(순진한 접근)

아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.

범위 변수로 정수 START 및 END를 사용합니다.
divisiblebyArr(int start, int end, int arr[], int len) 함수는 범위 변수와 배열을 가져와 모든 배열 요소로 나눌 수 있는 숫자의 개수를 반환합니다.
이러한 숫자에 대해 초기 변수 개수를 0으로 간주합니다.
변수 플래그를 0으로 사용
for 루프를 사용하여 숫자 범위를 탐색합니다. i=시작에서 i=끝
이제 각 숫자 num=i에 대해 while 루프를 사용하여 숫자가 모든 배열 요소로 나눌 수 있는지 확인합니다.
모든 요소가 num을 완전히 나누면 flag=1을 설정합니다.
외부 while if flag=1 증가 카운트
모든 루프의 끝에서 count는 배열의 모든 요소로 나눌 수 있는 총 수를 갖게 됩니다.
카운트를 결과로 반환합니다.

예시

#include <bits/stdc++.h>
using namespace std;
int divisiblebyArr(int start, int end, int arr[], int len){
   int count = 0;
   int flag=0;
   int index=0;
   for (int i = start; i <= end; i++){
      int num = i;
      index=0;
      while(index<len){
         if(num % arr[index++] == 0)
            { flag=1; }
         else{
            flag=0;
            break;
         }
      }
      if (flag == 1)
         { count++; }
      }
   return count;
}
int main(){
   int START = 5, END = 20;
   int Arr[] = {2,4,8 };
   int len=sizeof(Arr)/sizeof(Arr[0]);
   cout <<"Numbers that are divisible by all array elements: "<< divisiblebyArr(START,END,Arr,len);
   return 0;
}

출력

위의 코드를 실행하면 다음 출력이 생성됩니다 -

Numbers that are divisible by all array elements: 2

방법 2(LCM 접근법)

아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.

범위 변수로 정수 START 및 END를 사용합니다.
함수 getLCM(int a, int b)은 두 개의 숫자를 사용하고 while 루프를 사용하여 둘 다 나누어 떨어지는 첫 번째 숫자를 찾아 LCM을 반환합니다.
함수 getLCMArray(int arr[], int n)는 배열과 그 길이를 입력으로 사용하고 배열의 모든 요소에 대한 LCM을 반환합니다.
첫 번째 LCM을 getLCM(arr[0], arr[1])으로 계산합니다. 그 후 getLCM(lcm, arr[i])을 호출하여 이전 lcm의 lcm와 arr[i]를 차례로 찾습니다. 여기서 i=2 to i
divisiblebyArr(int start, int end, int arr[], int len) 함수는 범위 변수와 배열을 가져와 모든 배열 요소로 나눌 수 있는 숫자의 개수를 반환합니다.
이러한 숫자에 대해 초기 변수 개수를 0으로 간주합니다.
변수 lcm를 getLCMArray(int arr[], int len)로 사용합니다.
for 루프를 사용하여 숫자 범위를 탐색합니다. i=시작에서 i=끝
이제 각 숫자 i에 대해 나눌 수 있는 lcm인지 확인하십시오. true이면 카운트를 증가시킵니다.
모든 루프의 끝에서 count는 배열의 모든 요소로 나눌 수 있는 총 수를 갖게 됩니다.
카운트를 결과로 반환합니다.

예시

#include <bits/stdc++.h>
using namespace std;
int getLCM(int a, int b){
   int m;
   m = (a > b) ? a : b;
   while(true){
      if(m % a == 0 && m % b == 0)
         return m;
      m++;
   }
}
int getLCMArray(int arr[], int n){
   int lcm = getLCM(arr[0], arr[1]);
   for(int i = 2; i < n; i++){
      lcm = getLCM(lcm, arr[i]);
   }
   return lcm;
}
int divisiblebyArr(int start, int end, int arr[], int len){
   int count = 0;
   int flag=0;
   int lcm=getLCMArray(arr,len);
   for (int i = start; i <= end; i++){
      if(i%lcm==0)
         { count++; }
      }
   return count;
}
int main(){
   int START = 5, END = 20;
   int Arr[] = {2,4,8 };
   int len=sizeof(Arr)/sizeof(Arr[0]);
   cout <<"Numbers that are divisible by all array elements: "<< divisiblebyArr(START,END,Arr,len);
   return 0;
}

출력

위의 코드를 실행하면 다음 출력이 생성됩니다 -

Numbers that are divisible by all array elements: 2