크기가 N인 양의 정수 배열 Arr[]이 제공됩니다. 목표는 배열의 모든 요소의 곱에 존재하는 후행 0의 수를 계산하는 것입니다.
우리는 각 숫자의 요인을 계산하여 이를 수행할 것입니다. 우리는 2와 5를 각 숫자의 인수로 계산할 것입니다. 2와 5의 곱은 10이므로 1 뒤에 오는 0이 나옵니다. 결국에는 더 작은 개수가 제품의 뒤에 오는 0의 개수를 제공합니다. 4개의 2와 6개의 5가 있는 경우 제품에는 4개의 후행 0이 있습니다. 2*2*2*2*5*5*5*5*5*5=250000
예를 들어 이해합시다.
입력
Arr[] = { 2, 5, 10, 15, 20, 25, 100 } 출력
Number of trailing zeroes : 6
설명
Factors 2 and 5 of each element of Arr[]: Arr[0] = 2 : 2 twos=1, fives=0 Arr[1] = 5 : 5 twos=1, fives=1 Arr[2] = 10 : 2*5 twos=2, fives=2 Arr[3] = 15 : 3*5 twos=2, fives=3 Arr[4] = 20 : 2*2*5 twos=4, fives=4 Arr[5] = 25 : 5*5 twos=4, fives=6 Arr[6] = 100 : 2*2*5*5 twos=6, fives=8 Count of 2 is less so trailing zeroes will be 6.
입력
Arr[] = { 10,10,10,10,10 } 출력
Number of trailing zeroes : 5
설명
Factors 2 and 5 of each element of Arr[]: Arr[0] = 10 : 2*5 twos=1, fives=1 Arr[1] = 10 : 2*5 twos=2, fives=2 Arr[2] = 10 : 2*5 twos=3, fives=3 Arr[3] = 10 : 3*5 twos=4, fives=4 Arr[4] = 10 : 2*5 twos=5, fives=5 Count of 2 and 5 is equal so trailing zeroes will be 5.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
길이가 N인 양의 정수 배열을 사용합니다.
-
함수 trailZeros(int arr[],int n)는 배열과 n을 입력으로 사용하고 모든 요소의 곱에서 후행 0의 수를 반환합니다.
-
숫자 0에 대해 초기 변수 개수를 0으로 간주합니다.
-
두 개의 변수 2와 5를 인수로 2와 5를 셉니다.
-
for 루프를 사용하여 배열을 탐색합니다.
-
각 요소에 대해 2 또는 5로 나눌 수 있는 경우 2와 5를 늘리고 2 또는 5로 줄입니다.
-
for 루프의 끝에서 2와 5 중 더 작은 값을 확인합니다.
-
둘 중 작은 값으로 카운트를 초기화합니다.
-
카운트를 결과로 반환합니다.
예시
#include <bits/stdc++.h<
using namespace std;
int trailZeros(int arr[],int n){
int count = 0;
int twos = 0;
int fives = 0;
for (int i = 0; i < n; i++){
while(arr[i]%2==0 || arr[i]%5==0){
if(arr[i]%2==0){
arr[i]=arr[i]/2;
twos++;
}
if(arr[i]%5==0){
arr[i]=arr[i]/5;
fives++;
}
}
}
count=twos<fives?twos:fives;
return count;
}
int main(){
int Arr[]={ 12, 5 , 15, 8, 100, 40 };
int Length= sizeof(Arr)/sizeof(Arr[0]);
cout <<endl<< "Number of trailing zeroes : "<<trailZeros(Arr,Length);
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Number of trailing zeroes : 5