Cho số nguyên number. Nhiệm vụ: sắp xếp lại các chữ số của number sao cho số mới tạo ra cũng chia hết cho number.
Các trường hợp đầu vào/đầu ra
Đầu vào - int number = 100035
Đầu ra - Sắp xếp lại số chia hết cho số gốc: 300105
Giải thích - Số 100035. Sắp xếp chữ số thành 300105, số này chia hết cho 100035.
Đầu vào - int number = 1000035
Đầu ra - Sắp xếp lại số chia hết cho số gốc: 3000105
Giải thích - 3000105 chia hết cho 1000035.
Đầu vào - int number = 28
Đầu ra - Sắp xếp lại số chia hết cho số gốc: -1
Giải thích - Sắp xếp 28 thành 82, 82 không chia hết cho 28 → trả về -1.
Phương pháp sử dụng trong chương trình dưới đây
Nhập number, gọi Rearrangement(number).
Trong Rearrangement(number):
Tạo vector
vec(10,0) đếm tần suất chữ số. Gọi total_count(number, vec) đếm chữ số của number.
Vòng for i=2 đến 9: temp = number * i.
Tạo vec_2(10,0), gọi total_count(temp, vec_2).
Nếu vec và vec_2 giống nhau (equal) → trả về temp. Ngược lại trả về -1.
Hàm total_count(int number, vector
& vec_3): while(number>0) { vec_3[number%10]++; number/=10; }
Ví dụ mã
#include<bits/stdc++.h> using namespace std; void total_count(int number, vector<int> &vec_3){ while(number){ vec_3[number % 10]++; number = number / 10; } } int Rearrangement(int number){ vector<int> vec(10, 0); total_count(number, vec); for(int i = 2; i < 10; i++){ int temp = number * i; vector<int> vec_2(10, 0); total_count(temp, vec_2); if(equal(vec.begin(), vec.end(), vec_2.begin())){ return temp; } } return -1; } int main(){ int number = 100035; cout<<"Sắp xếp lại số chia hết cho số gốc: "<<Rearrangement(number); return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
Sắp xếp lại số chia hết cho số gốc: 300105