Giá trị lớn nhất của arr [i]% arr [j] cho một mảng nhất định trong C ++

Trong bài toán này, chúng ta được đưa ra một mảng gồm n phần tử. Nhiệm vụ của chúng ta là tạo một chương trình tìm giá trị lớn nhất của arr [i]% arr [j] cho một mảng nhất định.

Vì vậy, về cơ bản chúng ta cần tìm giá trị của phần dư lớn nhất trong khi chia hai phần tử của mảng.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào - mảng {3, 6, 9, 2, 1}

Đầu ra - 6

Giải thích -

3% 3 =0; 3% 6 =3; 3% 9 =3; 3% 2 =1; 3% 1 =06% 3 =0; 6% 6 =0; 6% 9 =6; 6% 2 =0; 6% 1 =09% 3 =0; 9% 6 =3; 9% 9 =0 9% 2 =1; 9% 1 =02% 3 =2; 2% 6 =2; 2% 9 =2; 2% 2 =0; 2% 1 =01% 3 =1; 1% 6 =1; 1% 9 =1; 1% 2 =1; 1% 1 =0 Trong số các phần còn lại ở trên, tối đa là 6.

Vì vậy, một cách tiếp cận trực tiếp để tìm lời giải sẽ là tính phần dư cho mỗi cặp và sau đó tìm giá trị lớn nhất của tất cả chúng. Nhưng cách tiếp cận này sẽ không hiệu quả vì độ phức tạp về thời gian sẽ theo thứ tự n ² .

Vì vậy, một giải pháp hiệu quả sẽ sử dụng logic rằng giá trị của x% y sẽ lớn nhất khi y> x thì phần dư sẽ là x. Và trong số tất cả các phần tử của mảng nếu chúng ta lấy hai phần tử lớn nhất thì kết quả sẽ là cực đại. Đối với điều này, chúng tôi sẽ sắp xếp mảng và sau đó lặp lại phần tử cuối cùng và phần tử cuối cùng thứ hai để cung cấp kết quả.

Ví dụ

Chương trình minh họa việc triển khai giải pháp của chúng tôi,

 #include  using namespace std; int maxRemainder (int arr [], int n) {bool hasSameValues =true; for (int i =1; i   Đầu ra 
  Phần còn lại lớn nhất khi chia hai phần tử của mảng là 6