วันพุธที่ 29 มิถุนายน พ.ศ. 2559

Project Euler 016: Power digit sum

โจทย์จาก : www.hackerrank.com
2^9 =  512  sum of its digits is 5 + 1 + 2 = 7 what is the sum of digits of  number 2^N
Input Format 
The first line contains an integer  , i.e., number of test cases. 
Next  lines will contain an integer .
Output Format 
Print the values corresponding to each test case.

Constraints
1<=T<=100
1<=N<=10000

แนวคิด
เนื่องจาก 2^N N สามารถมีค่ามากถึง 10000 ซึ่งไม่สามารถเก็บไว้ใน int หรือ long ได้ วิธีทำข้อนี้เราอาจจะใช้ Big Int เข้ามาช่วยหรือใช้ภาษาที่มี Big int ให้เรียกใช้ หรือไม่ก็ใช้แนวคิดการคูณเลขสมัยประถมเข้ามาแก้ก็ได้เหมือนกัน ในที่นี้ผมจะใช้วิธีการคูณเลขเข้ามาช่วย ผมสร้าง array ขนาดประมาณ5000 ช่องตัวนึงขึ้นมา array ตัวนี้จะเก็บผลคูณแต่ละหลัก โดนที่ array นี้จะเก็บจากหน้าไปหลัง เช่นถ้าเรามีเลข 128 array ของเราจะเก็บ [8,2,1,0,0,0,0,...] ทุกครั้งที่เราเอาเลข 2 ไปคูณแต่ละหลักค่าที่ได้อาจจะมากกว่า 10 หรือ น้อยกว่า 10 ก็ได้ แต่ในการคูณแต่ละหลักค่ามากสุดที่จะได้คือ 2*9 = 18 นั่นแสดงให้เห็นว่าเราจะได้ตัวเลข 2 ตัวคือตัว ทด กับ ตัวที่เป็นคำตอบของหลักนั้นๆ ถ้าคูณการในหลักแล้วได้ไม่ถึง 10 ตัวทดของเราก็จะเป็น 0 นั่นหมายความว่า ตัวทด = ผลคูณ/10 ส่วนคำตอบของหลัก = ผลคูณ % 10 นี่คือแนวคิด algorithm การคูณ แต่ว่าในการคูณแต่ละครั้งเราต้องคูณถึง 5000 รอบซึ่งถือว่าเสียเวลามาก ผมเลยหาว่าแต่ละรอบที่ 2 ยกกำลังมากขึ้นเรื่อยๆ จะมีกี่หลัก เพื่อที่จะทำให้ไวขึ้น โดยเราสามารถหาได้จาก จำนวนหลัก = (N*ln(2))/ln(10) และเพื่อทำให้โปรแกรมเราไวขึ้นเราสามารถเรียก N เป็น 10000 เพราะว่าเมื่อ N เป็น 10000 N ตั้งแต่ 1 ถึง 9999 ก็จะต้องถูกหาออกมาด้วย ในแต่ละรอบที่หา N มาได้ผมก็จะเก็บผลบวกไว้ลงไปใน array sum เหมือนเป็นการคิดคำตอบล่วงหน้าเอาไว้

สามารถเอาแนวคิดเขียนเป็นโค้ดได้แบบนี้ 
#include <iostream>
#include <iomanip>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
int main()
{
int sum[10002] = {0};
int arr[5000] = {0};
sum[1] = 2;
arr[0] = 2;
for(int i = 2;i<=10005;i++)
{
int itr = 0;
int carry = 0;
int k = ceil((i*log(2))/log(10));
while(itr<=k)
{
int product = arr[itr] * 2;
int digit = product % 10;
arr[itr] = digit + carry;
carry = product / 10;
itr++;
}
arr[itr] += carry;
for(int j = 0;j<=k;j++)
sum[i] += arr[j];
}
int tc;
cin >> tc;
while(tc-- > 0)
{
int n;
cin >> n;
cout << sum[n] << endl;
}
}

ไม่มีความคิดเห็น:

แสดงความคิดเห็น