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 เหมือนเป็นการคิดคำตอบล่วงหน้าเอาไว้

สามารถเอาแนวคิดเขียนเป็นโค้ดได้แบบนี้ 

Lattice Path

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a  grid? As number of ways can be very large, print it modulo (10^9 +7)

Constraints 

1 ≤ T ≤ 1000
1 ≤ N ≤ 500
1 ≤ M ≤ 500

โจทย์ข้อนี้ต้องการให้เราหาว่า ถ้าเราเริ่มจากจุดบนสุดฝั่งซ้ายลงจุดล่างสุดฝั่งขวา จะทำได้กี่วิธี ซึ่งถ้าดูแล้วเป็นโจทย์ที่ดูค่อนข้างจะง่าย เพราะสามารถใช้เรื่อง combinatorics เข้ามาแก้ได้ (N+M)!/(N!M!)
แต่ว่า  N กับ M อาจจะเป็นได้ถึง 500 ซึ่งค่าเยอะมาก ผมเลยไม่ได้ใช้สูตรนี้เข้ามาแก้ เมื่อผมลองมองหาวิธีอื่น ผมก็นึกถึง dynamic programming ผมเลยลองคิดว่าถ้าสี่เหลี่ยมขนาด 1*1 จะมีได้กี่วิธี และถ้า 2*1 จะมีได้กี่วิธี ผมลองเพิ่มหลักไปเรื่อยๆจนเป็น 1*6 แล้วลองเพิ่มแถวเป็น 2*1 3*1 ... 6*1 จนผมได้ตารางออกมา

ตอนแรกตารางนี้ไม่ได้มีแถวหรือหลักที่มี 1 แต่เมื่อผมเขียนตาราง 6*6 ออกมาแล้ว วิธีที่ M*N จะทำได้มีค่าเท่ากับ 
DP[i][j] = DP[i-1][j] + DP[i][j-1]  เช่นถ้าผมอยากรู้ว่า 1*1 ทำได้กี่วิธี

ผมสามารถหาได้จาก DP[1][1] = DP[0][1] + DP[1][0] , DP[0][1] = 1 DP[1][0] = 1 DP[1][1] จึงเท่ากับ 2 แต่ว่าโจทย์ข้อนี้เราต้องระวังเพราะเขาต้องการให้เรา mod(10^9+7) เพราะฉะนั้นในการสร้างตารางเราจะต้องทำการ mod ไม่ให้ค่าเกิน 10^9 +7 

( (a+b)%m = (a%m + b%m)%m) 

เราสามารถเอาไอเดียนี้เขียนเป็นโค้ดได้ 

สามารถไปลองทำกันได้ที่ www.hackerrank.com

Project Euler 014 - Longest Collatz sequence

โจทย์จาก : https://www.hackerrank.com/contests/projecteuler/challenges/euler014

ลำดับ Collatz สามารถสร้างได้โดย 3 เงื่อนใข 1.ถ้า n = 1 ให้ หยุด

                                   2.ถ้า n เป็นเลขคู่ ให้ n/2
                                   3.ถ้า n เป็นเลขคี่ ให้ 3n+1
เช่น n = 13 ลำดับก็จะเป็น 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 เมื่อ n = 13 ลำดับนี้จะมีความยาว = 10  โจทย์ข้อนี้ต้องการให้เราหาความยาวของลำดับที่มากที่สุด ที่ถูกสร้างโดยเลขที่ <= n
นั่นหมายความว่า ถ้า n เป็น 13 เราจะต้องไล่หาลำดับของ 13 , 12 , 11 ,10 ,...,1 แล้วดูว่าลำดับไหนมีความยาวมากที่สุด

แนวคิด ถ้ามองโจทย์ดีๆแล้วเมื่อเราสร้าง Collatz ของ 13 เราจะสร้างของ 40,20,10,5,16,8,2,1 เช่นเดียวกัน เพราะฉะนั้นเราสามารถใช้เทคนิคการ Memoization เข้ามาช่วยได้ จะทำให้เราสามารถหาลำดับ Collatz ได้ไวขึ้นมาก เมื่อเราหาได้แล้วเราจะต้องไล่ตั้ง 1 จนถึง n เพื่อหาว่าตัวไหนมากสุด แต่ถ้าหากคิดดีๆแล้ว
ถ้าเราจำค่าความยาวที่มากสุดแล้วนำไปเปรียบเทียบกับตัวถัดไปเรื่อยๆ เราก็สามารถทำการ precompute ทุกคำตอบได้เหมือนกัน

Project Euler 003 - Largest Prime factor - การหา prime factor ที่ใหญ่ที่สุด

โจทย์จาก : https://www.hackerrank.com/contests/projecteuler/challenges/euler003

โจทย์ข้อนี้ต้องการให้เราหาจำนวนเฉพาะที่ใหญ่ที่สุด และเป็นตัวประกอบของ N โดย
ที่ 10 <=N<= 10^12 
แนวคิด เมื่อผมเห็นข้อนี้ สิ่งที่ผมคิดไว้ตอนแรกคือการรันลูปไล่ตั้งแต่ 2 จนถึง N/2 เพื่อหาตัวที่หารลงตัว เมื่อได้ตัวที่หารลงตัว ก็นำไปเช็คต่อว่าเป็นจำนวนเฉพาะไหม แต่ถ้าลองคิดดีๆแล้วการที่ N มีค่าเยอะๆ แล้ว factor ของ N มีจำนวนเฉพาะที่ค่าเยอะ ก็จะเสียเวลาในการเช็คอย่างมาก ผมก็เลยนึกถึงการหา factor สมัยตอนมัธยมต้น เพราะเนื่องจากจำนวนเต็มบวกสามารถเขียนอยู่ในรูปผลคูณ
ของจำนวนเฉพาะได้

จากรูปด้านบน คือการหา factor ของ 160 เราเริ่มจากเอา 2 ซึ่งเป็นจำนวนเฉพาะที่เล็กที่สุด ที่สามารถหาร 160 ได้ไปหารจนกว่าจะหารไม่ได้ หากเราทำการหารด้วยจำนวนเฉพาะจนกว่าจะหารไม่ได้ไปเรื่อยๆแล้วๆ สุดท้ายแล้วเราก็จะได้จำนวนเฉพาะที่ใหญ่ที่สุดออกมา (จำนวนเฉพาะที่เล็กที่สุด ของจำนวนประกอบ N ใดๆ จะมีค่าน้อยกว่าหรือเท่ากับ sqrt(N))

เราสามารถนำแนวคิดนี้ไปเขียนเป็นโค้ดในภาษาซีได้แบบนี้