Interview Question Analysts
dynamic programing will do the job
long fact(int n) {
long []F=new long[n+1];
F[1]=1;
F[0]=1;
for(int i=1;i<=n;i++){
F[i]=i*F[i-1];
//System.out.println(F[n]);
} return F[n];
}
const int VALUE = 1000; // Number of factorial to find
int Result[VALUE] = {0}; // all number is 0
Result[VALUE - 1] = 1; // last number is 1
int Difference = 0;
for(int X = 1; X <= VALUE; X++)
{
X=X;
for(int Y = VALUE - 1; Y > -1; Y --)
{
Result[Y] = Result[Y] * X + Difference;
Difference = 0;
if(Result[Y] > VALUE)
{
Difference = Result[Y] / VALUE;
Result[Y] = Result[Y] - Difference * VALUE;
}
}
}
for(int i=0; i<VALUE; i++)
std::cout << Result[i];
Code not actually true, here is fix:
// To find
const int FACTORIAL_N = 10;
// Dimension of array - let it be like N (we don't know for large numbers)
const int DIMENSION = FACTORIAL_N;
// Array of numbers
int Vals[DIMENSION] = {0};
// Fill array from the end like: 0..01, 0..02, etc.
Vals[DIMENSION-1]=1;
// Max value for the ONE item of array (could be 10, 100, 1000, etc. any)
int item = 10;
// Difference to grow next rank
int Temp = 0;
for(int X = 1; X <= FACTORIAL_N; X++)
for(int Y = DIMENSION-1; Y > -1; Y--)
{
Vals[Y] = Vals[Y] * X + Temp;
Temp = 0;
if(Vals[Y] > item-1)
{
Temp = Vals[Y] / item;
Vals[Y] = Vals[Y] - Temp * item;
}
}
for(int i=0; i<DIMENSION; i++)
cout << Vals[i];
<pre lang="java" line="1" title="CodeMonkey83657" class="run-this">package com.saral.careercup.amazon;
import java.util.ArrayList;
import java.util.List;
public class FactorialOfLargeNumber {
public static void main(String[] args) {
int n = 35;
int [] factorial = factorial(n);
boolean start = false;
for(int i=0; i<factorial.length; i++){
if (factorial[i] != 0){
start = true;
}
if(start)
System.out.print(factorial[i]);
}
System.out.println();
}
public static int[] factorial(int n){
int[] result = toIntegerArray(1);
for(int i=2; i<=n; i++){
result = multiply(result, toIntegerArray(i));
}
return result;
}
public static int[] toIntegerArray(int i){
int[] array = new int[String.valueOf(i).length()];
int k=array.length;
while(k>=0){
if(i < 10){
array[--k] = i;
break;
}else{
int r = i % 10;
array[--k] = r;
i = i / 10;
}
}
return array;
}
public static int[] multiply(int[] a, int[] b){
List<int[]> list = new ArrayList<int[]>();
int l = 0;
for(int i=a.length-1; i>=0; i--){
int carry = 0;
int[] r = new int[a.length + b.length + 1];
int k = r.length-++l;
for(int j=b.length-1; j>=0; j--, k--){
int p = (a[i] * b[j]) + carry;
r[k] = p % 10;
carry = p/10;
}
r[k] = r[k] + carry;
list.add(r);
}
return sum(list);
}
public static int[] sum(List<int[]> intList){
int[] sum = null;
int maxLength = 0;
for(int[] i: intList){
if(i.length > maxLength)
maxLength = i.length;
}
sum = new int[maxLength + 1];
for(int i = 0; i<intList.size(); i++){
for(int k=intList.get(i).length-1, l=sum.length-1; k>=0; k--, l--){
int s = sum[l] + intList.get(i)[k];
sum[l] = s % 10;
sum[l-1] = sum[l-1] + (s / 10);
}
}
return sum;
}
}
</pre><pre title="CodeMonkey83657" input="yes">
</pre>
<pre lang="java" line="1" title="CodeMonkey96989" class="run-this">package com.saral.careercup.amazon;
import java.util.ArrayList;
import java.util.List;
public class FactorialOfLargeNumber {
public static void main(String[] args) {
int n = 35;
int [] factorial = factorial(n);
boolean start = false;
for(int i=0; i<factorial.length; i++){
if (factorial[i] != 0){
start = true;
}
if(start)
System.out.print(factorial[i]);
}
System.out.println();
}
public static int[] factorial(int n){
int[] result = toIntegerArray(1);
for(int i=2; i<=n; i++){
result = multiply(result, toIntegerArray(i));
}
return result;
}
public static int[] toIntegerArray(int i){
int[] array = new int[String.valueOf(i).length()];
int k=array.length;
while(k>=0){
if(i < 10){
array[--k] = i;
break;
}else{
int r = i % 10;
array[--k] = r;
i = i / 10;
}
}
return array;
}
public static int[] multiply(int[] a, int[] b){
List<int[]> list = new ArrayList<int[]>();
int l = 0;
for(int i=a.length-1; i>=0; i--){
int carry = 0;
int[] r = new int[a.length + b.length + 1];
int k = r.length-++l;
for(int j=b.length-1; j>=0; j--, k--){
int p = (a[i] * b[j]) + carry;
r[k] = p % 10;
carry = p/10;
}
r[k] = r[k] + carry;
list.add(r);
}
return sum(list);
}
public static int[] sum(List<int[]> intList){
int[] sum = null;
int maxLength = 0;
for(int[] i: intList){
if(i.length > maxLength)
maxLength = i.length;
}
sum = new int[maxLength + 1];
for(int i = 0; i<intList.size(); i++){
for(int k=intList.get(i).length-1, l=sum.length-1; k>=0; k--, l--){
int s = sum[l] + intList.get(i)[k];
sum[l] = s % 10;
sum[l-1] = sum[l-1] + (s / 10);
}
}
return sum;
}
}
</pre><pre title="CodeMonkey96989" input="yes">This code prints the value of 35!
</pre>
<pre lang="c++" line="1" title="CodeMonkey36722" class="run-this">vector<int> num2list(int n) {
vector<int> result;
while (n) {
result.push_back(n%10);
n /= 10;
}
return result;
}
vector<int> multiply_list(const vector<int> &list1, const vector<int> &list2) {
vector<int> result;
int start_from = 0;
for (int i=0; i<list2.size(); i++) {
int carry_in = 0;
for (int j=0; j<list1.size(); j++) {
int product = list2[i] * list1[j];
if (start_from+j < result.size()) {
result[start_from+j] = (product + carry_in) % 10;
carry_in = (product + carry_in) / 10;
} else {
result.push_back((product + carry_in) % 10);
}
carry_in = (product + carry_in) / 10;
}
if (carry_in)
result.push_back(carry_in);
start_from++;
}
return result;
}
vector<int> factorial(int n) {
vector<int> result(1, 1);
for (int i=2; i<=n; i++) {
vector<int> multiplier = num2list(i);
result = multiply_list(result, multiplier);
}
reverse(result.begin(), result.end());
return result;
}
</pre><pre title="CodeMonkey36722" input="yes">
</pre>
#include<iostream>
using namespace std;
int main()
{
int numArr[3000]; // Approximately , size of array depends on size of factorial.
int total,rem=0,count; //rem use to save remainder of division(Carry Number).
register int i;
for(i=0;i<3000;i++)
numArr[i]=0; //set all array on NULL.
i=2999; //start from end of array.
numArr[2999]=1;
for(count=2;count<=1000;count++)//Refer to my article for more explanation.
{
while(i>0)
{
total=numArr[i]*count+rem;
rem=0;
if(total>9)
{
numArr[i]=total%10;
rem=total/10;
}
else
numArr[i]=total;
i--;
}
rem=0;
total=0;
i=2999;
}
for(i=0;i<3000;i++) // Display array's cell to show factorial 1000
{
if(numArr[i]!=0 | count==1)
{
cout<<numArr[i];
count=1;
}
}
}
Cheers
A improvement to the solution of amd.anand, we can combine the multiple and sum methods into just one method..
What I do is instead of calculating the carry bit every time. I just create a single array instead of list of int[] and keep on adding the values in the same element. And in a separate for loop at the end, calculate the carry bit and move it to the next element.
This is also the way it is implemented in BitInteger class
public static int[] multiply(int[] x, int xlen, int[] y, int ylen) {
int[] tempArray = new int[xlen + ylen];
int k;
for (int i = ylen - 1; i >= 0; i--) {
k = tempArray.length - (ylen - i);
for (int j = xlen - 1; j >= 0; j--) {
tempArray[k--] += y[i] * x[j];
}
}
int[] result = new int[tempArray.length];
for (int n = tempArray.length - 1; n > 0; n--) {
result[n] = tempArray[n] % 10;
tempArray[n - 1] += tempArray[n] / 10;
}
return result;
}
//Using T. J. Stieltjes method for big factorial >.> try to do that in an interview!
//only issue is the != to compare 2 float... I know...
//Hoping it would stop if the value added is so little that it is ignored...
//Should work, but best would be to have a checkup for difference...
//I just feared we can't checkup for how big the difference is when you are in super big values of 3*10^997 and higher, can't really compare if the difference is bigger then 0.1 ^^
factorial(int x) {
long double fo=0;
long double fn=0;
while (fo!=fn) {
fo=fn;
fn=fo+log(2*PI)/2-x+(x+0.5)*log(x)
}
return fn;
}
codingskills4u.com/2013/02/simple-recursive-program-to-find.html
- dhina March 27, 2013