จำนวนการเคลื่อนที่น้อยที่สุดเพื่อทำให้สมาชิกทั้งหมดเท่ากันด้วย C++

ข้อความโจทย์

กำหนดอาร์เรย์ N สมาชิก และจำนวนเต็ม K สามารถทำการดำเนินการต่อไปนี้ได้จำนวนครั้งไม่จำกัดบนอาร์เรย์ที่กำหนด -

• นำสมาชิกลำดับที่ K ไปต่อท้ายอาร์เรย์ และลบสมาชิกตัวแรกของอาร์เรย์

งานคือหาจำนวนการเคลื่อนที่น้อยที่สุดที่จำเป็นเพื่อทำให้สมาชิกทั้งหมดของอาร์เรย์เท่ากัน พิมพ์ -1 หากไม่เป็นไปได้

ถ้า arr[] = {1, 2, 3, 4, 5, 6} และ k = 6 แล้วต้องการ 5 การเคลื่อนที่ขั้นต่ำ:
Move-1: {2, 3, 4, 5, 6, 6}
Move-2: {3, 4, 5, 6, 6, 6}
Move-3: {4, 5, 6, 6, 6, 6}
Move-4: {5, 6, 6, 6, 6, 6}
Move-5: {6, 6, 6, 6, 6, 6}

อัลกอริทึม

1. ก่อนอื่นเราคัดลอก a[k] ไปท้าย แล้ว a[k+1] และต่อไป
2. เพื่อให้แน่ใจว่าเราคัดลอกเฉพาะสมาชิกที่เท่ากัน ทุกสมาชิกในช่วง K ถึง N ควรเท่ากัน เราต้องลบสมาชิกทั้งหมดในช่วง 1 ถึง K ที่ไม่เท่ากับ a[k]
3. ทำการดำเนินการซ้ำจนถึงพจน์ขวาสุดในช่วง 1 ถึง K ที่ไม่เท่ากับ a[k]

ตัวอย่างโค้ด

#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

int getMinMoves(int *arr, int n, int k) {
    int i;
    for (i = k - 1; i < n; ++i) {
        if (arr[i] != arr[k - 1]) {
            return -1;
        }
    }
    for (i = k - 1; i >= 0; --i) {
        if (arr[i] != arr[k - 1]) {
            return i + 1;
        }
    }
    return 0;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6};
    int k = 6;
    cout << "Minimum moves required = " << getMinMoves(arr, SIZE(arr), k) << endl;
    return 0;
}

ผลลัพธ์

เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้ -

Minimum moves required = 5