11621 - Small Factors
Solution Description : DP and Binary Search problem Find fist 330 C23[] number using the given method below. Fist few C23 number: 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96 (all number are multiple of 2 or 3 or both) 1. set C23[0]=1; 2. set position for 2,and 3 are 0 i.e. pos2=pos3=0; 3. find minimum value from C23[pos2]*2, C23[pos3]*3 4. store the minimum value to C23[i++] 5. C23[pos2]*2==min then pos2++, C23[pos3]*3==min then pos3++ After than find the upper bound from C23[] array for given input n using binary search. You can user C++ stl upper_bound() method. |
||||||||||