Thao tác mảng và tính tổng bằng C / C ++

Ở đây chúng ta sẽ thấy một vấn đề, giả sử một mảng được đưa ra. Có n phần tử. Một giá trị khác S cũng được đưa ra. Chúng ta phải tìm một phần tử K trong mảng, sao cho nếu tất cả các phần tử lớn hơn K, đều bằng K, thì tổng tất cả các phần tử của mảng cuối cùng sẽ bằng S. Nếu không thể, sau đó trả về -1.

Giả sử các phần tử là {12, 6, 3, 7, 8} và giá trị tổng là 15, kết quả là 3. Mảng cuối cùng là {3, 3, 3, 3, 3}, Tổng các phần tử của mảng là S =15

Thuật toán

getVal (arr, n, S) -

Begin
   sort arr as increasing order
   sum := 0
   for i in range 0 to n-1, do
      if sum + (arr[i] * (n - i)) is same as S, then
         return arr[i]
      end if
      sum := sum + arr[i]
   done
   return -1
End

Ví dụ

#include <iostream>
#include <algorithm>
using namespace std;
int getVal(int arr[], int n, int S) {
   sort(arr, arr + n);
   int sum = 0;
   for (int i = 0; i < n; i++) {
      if (sum + (arr[i] * (n - i)) == S) //if current value is satisfying, then return arr[i]
         return arr[i];
      sum += arr[i];
   }
   return -1;
}
int main() {
   int S = 15;
   int arr[] = { 12, 3, 6, 7, 8 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << getVal(arr, n, S);
}

Đầu ra

3