Số lớn nhất bằng cách nối mọi phần tử trong một phép xoay của mảng trong C++

Chúng ta được cho một mảng vòng tròn các số. Mảng vòng tròn là mảng mà các phần tử được sắp xếp sao cho phần tử đầu tiên được xem như ngay sau phần tử cuối cùng. Chúng được dùng để triển khai hàng đợi.

Mỗi phần tử có số chữ số giống hoặc khác nhau. Mục tiêu là tạo số lớn nhất có thể bằng cách nối các số, sử dụng phép xoay phần tử nếu cần. Chúng ta sẽ làm bằng cách tìm chữ số trái nhất lớn nhất trong tất cả chữ số trái nhất của tất cả phần tử. Số có chữ số trái nhất lớn nhất sẽ lấy vị trí đầu tiên.

• Nếu nó ở vị trí đầu tiên, tất cả số tại chỉ số 1 đến n-1 được đặt như cũ.
• Nếu nó ở giữa đâu đó, và chỉ số của nó là i, tất cả tại chỉ số i+1 đến n-1 được nối trước theo sau bởi các chỉ số 0 đến i-1.
• Nếu nó là cuối cùng, thì tất cả tại chỉ số 0 đến i-1 được nối sau nó.

Ví dụ

Đầu vào

Arr[] = { 121, 43, 65, 32 }

Đầu ra

Số lớn nhất: 653212143

Giải thích − Chữ số trái nhất lớn nhất là 6. Đặt 65 ở vị trí đầu theo sau 32, rồi 121, 43. Vì Arr[] là mảng vòng tròn.

Đầu vào

Arr[] = { 1101, 9, 321, 77 }

Đầu ra

Số lớn nhất: 9321771101

Giải thích − Chữ số trái nhất lớn nhất là 9. Đặt 9 ở vị trí đầu theo sau 321, rồi 77, 1101. Vì Arr[] là mảng vòng tròn.

Phương pháp sử dụng trong chương trình dưới đây

• Mảng arr[] lưu số.
• Hàm Largest(int arr[], int n) nhận mảng và độ dài n, in ra số lớn nhất có thể tạo.
• Biến maxx lưu số có chữ số trái nhất lớn nhất, khởi tạo 0.
• Pos lưu chỉ số của maxx.
• Bắt đầu từ i=0 đến n tìm chữ số trái nhất của mỗi arr[i] bằng cách chia cho 10 cho đến khi nó thành 0. Mỗi lần phần dư đại diện cho chữ số hàng đơn vị.
• Nếu chữ số hiện tại như vậy lớn nhất, khi num == 0 (nghĩa rem có chữ số trái nhất), cập nhật maxx và pos.
• In các phần tử từ chỉ số pos đến cuối mảng rồi lại từ chỉ số 0 đến pos-1.

Ví dụ mã nguồn

#include <bits/stdc++.h> 
using namespace std; 

void Largest(int arr[], int n) { 
    int maxx = 0; 
    int pos = 0; // chỉ số số có chữ số trái nhất lớn nhất
    for (int i = 0; i < n; i++) { 
        int num = arr[i]; 
        // kiểm tra chữ số cuối cùng
        while (num != 0) { 
            int rem = num % 10; 
            num = num / 10; 
            if (num == 0) { 
                if (maxx < rem) { 
                    maxx = rem; 
                    pos = i; 
                } 
            } 
        } 
    } 
    // in số lớn nhất
    cout << "Số lớn nhất bằng nối: "; 
    for (int i = pos; i < n; i++) 
        cout << arr[i]; 
    for (int i = 0; i < pos; i++) 
        cout << arr[i]; 
} 

int main() { 
    int Arr[] = { 12, 34, 56, 98 }; 
    int size = 4; 
    Largest(Arr, size); 
    return 0; 
}

Kết quả

Số lớn nhất bằng nối: 98123456