ในปัญหานี้ เราได้รับจำนวนเต็ม n งานของเราคือ หาผลรวมของหลักที่ใหญ่ที่สุดในตัวหารทั้งหมดของ n
คำอธิบายปัญหา: ในที่นี้ เราจะหาตัวหารของจำนวน n ซึ่งมีผลรวมของหลักมากที่สุด
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล: 18
ผลลัพธ์: 9
คำอธิบาย:
ตัวหารทั้งหมดของ 18 คือ 1, 2, 3, 6, 9, 18
ผลรวมตัวเลขสูงสุดคือ 9
แนวทางการแก้ปัญหา
หาตัวหารทั้งหมดของเลข N แล้วหาผลรวมหลักของตัวหารแต่ละตัว แล้วคืนค่าด้วยผลรวมที่มากที่สุด
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include <iostream>
using namespace std;
int calcDigitSum(int n) {
int sum = 0;
while (n != 0) {
sum = sum + n % 10;
n = n/10;
}
return sum;
}
int largestDigitSumdivisior(int n) {
int maxSum = 0;
for (int i = 1; i <= n; i++)
if (n % i == 0)
maxSum = max(maxSum, calcDigitSum(i));
return maxSum;
}
int main() {
int n = 45;
cout<<"The divisor with largest sum of digits is "<<largestDigitSumdivisior(n)<<endl;
return 0;
} ผลลัพธ์
The divisor with largest sum of digits is 9
การแก้ปัญหาสามารถทำได้อย่างมีประสิทธิภาพมากขึ้นโดยใช้การปรับเปลี่ยนวิธีการเพื่อหาตัวหารและทำให้มีประสิทธิภาพมากขึ้น
ในปัญหานี้ เราจะวนซ้ำจนถึง sqrt(n) และค้นหาตัวหารทั้งหมดและตัวหารอื่นๆ คำนวณโดยใช้ n/div ซึ่งจะช่วยลดความซับซ้อนของเวลาในการหาตัวหารเป็น sqrt(n)
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include <iostream>
using namespace std;
int calcDigitSum(int n) {
int sum = 0;
while (n != 0) {
sum = sum + n % 10;
n = n / 10;
}
return sum;
}
int largestDigitSumdivisior(int n) {
int maxSum = 0;
for (int i = 1; i*i <= n; i++) {
if (n % i == 0) {
maxSum = max(maxSum, calcDigitSum(i));
maxSum = max(maxSum,calcDigitSum(n/i));
}
}
return maxSum;
}
int main() {
int n = 32;
cout<<"The divisor with largest sum of digits is "<<largestDigitSumdivisior(n)<<endl;
return 0;
} ผลลัพธ์
The divisor with largest sum of digits is 8
