Độ khó: Khó (4/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

---

Bài toán được chuyển sang dạng nhập/xuất chuẩn (stdin/stdout).

Cho một mảng số nguyên nums. Trong một phép biến đổi, bạn có thể thay bất kỳ phần tử nào của nums bằng một số nguyên bất kỳ.

Mảng nums được gọi là liên tục nếu thỏa mãn cả hai điều kiện sau:

• Mọi phần tử trong nums đều đôi một khác nhau.
• Hiệu giữa phần tử lớn nhất và phần tử nhỏ nhất của nums bằng nums.length - 1.

Ví dụ, nums = [4, 2, 5, 3] là liên tục, nhưng nums = [1, 2, 3, 5, 6] thì không liên tục.

Yêu cầu: in ra số phép biến đổi ít nhất để nums trở nên liên tục.

Dữ liệu vào

• Dòng đầu tiên gồm số nguyên ~n~ là độ dài mảng nums.
• Dòng thứ hai gồm ~n~ số nguyên nums[0], nums[1], ..., nums[n-1].

Kết quả

• In ra một số nguyên duy nhất là số phép biến đổi ít nhất.

Giới hạn

• ~1 \le n \le 10^5~.
• ~1 \le~ nums[i] ~\le 10^9~.

Sample Input 1

4
4 2 5 3

Sample Output 1

0

Giải thích

nums đã liên tục sẵn rồi.

Sample Input 2

5
1 2 3 5 6

Sample Output 2

1

Giải thích

Một cách làm là đổi phần tử cuối thành 4. Mảng thu được là [1,2,3,5,4], là mảng liên tục.

Sample Input 3

4
1 10 100 1000

Sample Output 3

3

Giải thích

Một cách làm là: đổi phần tử thứ hai thành 2; đổi phần tử thứ ba thành 3; đổi phần tử thứ tư thành 4. Mảng thu được là [1,2,3,4], là mảng liên tục.

Nguồn: LeetCode 2009.