컨셉
M개의 정수로 구성된 두 개의 주어진 배열과 관련하여 배열 C를 가정합니다. 여기서 i번째 정수는 d*a[i] + b[i]가 됩니다. 여기서 d는 임의의 실수로 표시됩니다. 우리의 임무는 배열 C가 가장 많은 수의 0을 갖고 또한 0의 수를 출력하도록 d를 표시하거나 출력하는 것입니다.
입력
a[] = {15, 40, 45}
b[] = {4, 5, 6} 출력
Value of d is: -0.133333 The number of zeros in array C is: 1 If we choose d as -0.133333 then we get one zero in the array C which is the maximum possible.
방법
우리는 위의 문제를 해결하기 위해 아래 언급된 단계를 따릅니다 -
- 방정식을 d =-b[i]/a[i]로 다시 작성합니다.
- d 값을 얻기 위해 실수가 가장 많이 발생하는 횟수를 계산하는 해시 테이블을 구현합니다.
- 이제 0의 개수가 가장 큰 개수 + (둘 다 0인 경우 a[i] 및 b[i] 쌍의 개수)가 될 것이라는 결론을 내립니다.
예시
// C++ program to implement the above
// approach
#include <bits/stdc++.h>
using namespace std;
// Shows function to find the value of d
// and find the number of zeros in the array
void findDandZeros1(int a[], int b[], int m){
// Shows hash table
unordered_map<long double, int> mpp1;
int count1 = 0;
// Performs iteration for i-th element
for (int i = 0; i < m; i++) {
// Now if both are not 0
if (b[i] != 0 && a[i] != 0) {
long double val1 = (long double)(-1.0 * b[i]) /
(long double)(a[i]);
mpp1[val1] += 1;
}
// Now if both are 0
else if (b[i] == 0 && a[i] == 0)
count1 += 1;
}
// Used to find max occurring d
int maxi1 = 0;
for (auto it : mpp1) {
maxi1 = max(it.second, maxi1);
}
// Used to print the d which occurs max times
for (auto it : mpp1) {
if (it.second == maxi1) {
cout << "Value of d is: "
<< it.first << endl;
break;
}
}
// Used to print the number of zeros
cout << "The number of zeros in array C is: "
<< maxi1 + count1;
}
// Driver code
int main(){
int a[] = { 15, 40, 45 };
int b[] = { 4, 5, 6 };
int m = sizeof(a) / sizeof(a[0]);
findDandZeros1(a, b, m);
return 0;
} 출력
Value of d is: -0.133333 The number of zeros in array C is: 1