Trong bài toán này, chúng ta được cung cấp một mảng arr [] có kích thước N và một giá trị nguyên M. Nhiệm vụ của chúng ta là tìm vị trí của phần tử bị loại bỏ cuối cùng khỏi mảng .
Việc loại bỏ các giá trị khỏi mảng dựa trên các phép toán -
- Đối với một phần tử trong mảng arr [i]. Nếu arr [i]> M, bật giá trị và đẩy arr [i] - M xuống cuối mảng. Nếu không, hãy xóa nó khỏi mảng.
Thực hiện các phép toán cho đến khi mảng bao gồm các phần tử.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {5, 4, 8}, M = 3 Đầu ra
3
Giải thích
Removing values using operations,
{5, 4, 8} -> {4, 8, 2} -> {8, 1, 2} -> {1, 2, 5} -> {2, 5} -> {5} -> {2} ->
empty array.
The last value removed is 8, position is 3. Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là tìm giá trị cuối cùng cần loại bỏ với thực tế là mỗi giá trị sẽ bị loại bỏ cuối cùng có giá trị lớn nhất là ceil (arr [i] / M) .
Để tìm vị trí của các phần tử thoát khỏi mảng cuối cùng, chúng tôi sẽ duyệt qua mảng và lưu trữ vị trí có giá trị lớn nhất là ceil (arr [i] / M) .
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#include <iostream>
using namespace std;
int findLastRemPos(int arr[], int n, int m){
for (int i = 0; i < n; i++) {
arr[i] = (arr[i] / m + (arr[i] % m != 0));
}
int lastRemPos = -1, largestVal = -1;
for (int i = n - 1; i >= 0; i--) {
if (largestVal < arr[i]) {
largestVal = arr[i];
lastRemPos = i;
}
}
return lastRemPos + 1;
}
int main(){
int arr[] = {5, 4, 8, 1};
int n = sizeof(arr) / sizeof(arr[0]);
int m = 3;
cout<<"The position of last removed element in the array is "<<findLastRemPos(arr, n, m);
return 0;
} Đầu ra
The position of last removed element in the array is 3