Small factorials | CodeChef

help
1

So this problem has kicked my butt for almost a week. Below is what I’ve got after beating my head against my desk. Please help! Also, how does the temp variable get its value? Would it be temp = x/10?

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
	    Scanner in = new Scanner (System.in);
	    System.out.println("Please enter a number to test: ");
	    int testCase = in.nextInt();
	  
		int [] array = new int [testCase];
		
		for (int i = 0; i < array.length; i++){
		    int temp, n, sum =0;
		    
		    temp = array[i];
		    
		}
	}
}
2

Statements such as these are not required in CP. You must strictly adhere to the given input / output format.

I suggest you to get up and code, because this code of yours does nothing related to this problem.


In case you don’t know what factorials are, you might want to look here.

3

Asking for an input is proper/good coding. If you don’t input something, how is the computer going to know what to calculate? I do know factorial’s, but am having issues programming the code. Another issue that I cannot grasp is how to add 120 into each index, starting at [0], [1], [3]. I’m trying to learn.

4

I have now read that asking for input is frowned upon on a few posts, but no one really explains why, or indicates how you should input information. Would it be long sum = in.nextLong(); exclusively? Again, why is asking for user input bad?

5

In competitive programming, you should perform input / output operations exactly as required in the problem statement. This is because your code is being evaluated by an online judge, which returns the verdict based on what your code prints to “standard output”. When you write statements such as "Please enter a number", this gets printed on the standard output too, thus giving a non AC verdict, even though your logic / algorithm maybe correct.

I guess you should go through some articles such as this or maybe watch some YouTube videos such as this about competitive programming (there are quite a few of them out there), to get started.

6

So I’m not sure as to where else to start. I get stuck and aren’t sure where else to go/look. I don’t want to rely too heavily on looking up code and then regurgitating what I found. I’ve taken two classes at the university I attend, and it seems that is what they teach. I’m really trying to learn how to properly program. Any help would be greatly appreciated.

7

Can someone tell me how the temp variable gets updated?

" At every iteration, we calculate 37 * a [index]. We also maintain a temporary variable called temp which is initialized to 0. Now, at every step, we calculate x = a[index] * 37 + temp . The new value of a [index] will be x % 10 and the new value of temp will be temp / 10

I’m thinking it is like the following:

temp = 0;
x = array [0] * 37 + temp;
array [0] = x % 10;
temp = x/10;

Would that be how temp gets updated? I know it needs to run in a loop as well but aren’t sure how to implement it into a loop.

8

What shit is this…?
Really Are You talking about factorials…?

9

This shit, M’kay

The least significant digit is stored in the lowest index 0. The next one in index 1 and so on. Along with the array, we need an integer specifying the total number of digits in the array at the given moment. Let this number be ‘ m ‘. Initially, a [0] will be 1 and the value of ‘ m ‘ will be 1 specifying that we have just one digit in the array.

Let’s take a simple example first. Consider that the array has some value like 45 and we need to multiply it with a value 37. This can be done in the following way.
The array will be:
a [0] = 5
a [1] = 4
and the value of m will be 2 specifying that there are 2 digits in the array currently.

Now, to multiply this array with the value 37. We start off from the index 0 of the array to index 1. At every iteration, we calculate 37 * a [index]. We also maintain a temporary variable called temp which is initialized to 0. Now, at every step, we calculate x = a[index] * 37 + temp . The new value of a [index] will be x % 10 and the new value of temp will be temp / 10 . We are simply carrying out multiplication the way it is carried out usually. So, for the current situation, the iterations will be something like this.

Initialize temp = 0
Iteration 1 :
array = (5, 4)
temp = 0
index = 0, a[index] = 5
x = a[index] * 37 + temp = 5 * 37 + 0 = 185.
the new value of a[index] = 185 % 10 which is 5 and the new value of temp is 185 / 10 which is 18

Iteration 2 :
array : (5, 4)
temp = 18
index = 1, a[index] = 4
x = a[index] * 37 + temp = 4 * 37 + 18 = 166.
the new value of a[index] = 166 % 10 which is 6 and the new value of temp is 166 / 10 which is 16

We have finished 2 iterations and this is the value of ‘ m ‘, the array size at the moment. The required number of iterations is now over, but the value of temp is still greater than 0. This means that the current value of temp is to be incorporated into the array. For that, we keep appending the last digit of temp to the array and divide temp by 10 till temp becomes 0. So, we will get something like
Iteration 1 :
temp = 16 , array = (5, 6)
So, we add 16 % 10 to the array so that the array becomes (5, 6, 6) and we divide temp by 10 so that temp becomes 1. We update the value of ‘m’ to m + 1 that is m = 3
Iteration 2 :
temp = 1, array = (5, 6, 6)
Now, we add 1 % 10 to the array so the array becomes (5, 6, 6, 1) and we divide temp by 10 so that temp becomes 0. We update the value of ‘m’ to m + 1 that is m = 4

The value of temp is now 0 and our multiplication is now over. The final array we get is (5, 6, 6, 1)

Voila, we have the answer to 45 * 37 in our array with the Least significant digit in the 0th position. :slightly_smiling_face:

10

that was just an EXAMPLE

11

Exactly. And when you’re new and looking for help, what do you THINK you might would look to for help?

12

Ok, I am sorry… I will help you in solving this ques.

13

Here is the minified version solution with full AC
an this is the descriptive one
I really took a lot of time writing the explanation

If you still have queries, feel free to ask

import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
    public static void multiply(int arr[], int num){
        
        int index=0;
        while(arr[index]==0)index++;
        int i=199;
        int carry=0;
        while(i>=index){
            int product=arr[i]*num;
            arr[i]=(product+carry)%10;
            carry=(product+carry)/10;
            i--;
        }
        index--;//if we have some carry reamining
        while(carry!=0){
            arr[index]=(carry%10);
            carry=carry/10;
            index--;
        }
    }
    public static void fact(int arr[],int num){
        
        for(int i=num-1;i>1;i--){//num-1 coz' we don't have to multiply the num by itself
            multiply(arr,i);
        }
        
    }
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc = new Scanner(System.in);
		int t=Integer.parseInt(sc.nextLine());//try to read full lines, at least in Java
		
		for(int i=0;i<t;i++){//loop for testcases
		
		    int arr[]=new int[200];//all elems will be 0s
		    //since, above array is *created* in loop, so a new instance will be created at every loop call
		    
		    int n=Integer.parseInt(sc.nextLine());//input no.
		    
		    int c=n;//copying n, we will use that later
		    
		    int ind=200-1;//the last index
		    
		    //The next is to represent the number in array
		    while(n!=0){
		        arr[ind]=n%10;//last digit
		        n=n/10;//remove last digit
		        ind--;//get next index
		    }//do this till n becomes 0;
		    
		    fact(arr, c);//call the function, we use the copied value of n
		    
		    int index = 0;
		    while(arr[index]==0)index++; //we get the first index from where the number starts
		    //now print this Number
		    
		    for(int j=index;j<arr.length;j++){//arr.length is 200
		    
		        //get the digit by arr[j]
		        System.out.print(arr[j]);//see I have used print here, not println bcoz we have to print the digits in the same line
		        
		    }
		    System.out.println();//At last end this line;
		}
	}
}
14

But as an absolute beginner, you shoud try more easy questions

15

I agree, but this is the fourth “easy” program on the list. I’ve had small issues with others, but they’ve amped up the difficulty level with this problem. I will look over the solution you’ve posted. I do understand a big portion of it but will ask questions as needed. Thank you for your assistance.

1 Like
16

Can you explain these a little better, please? I’m reading in my books to try and understand when and why to use those in arrays. I understand they’re a wrapper for Strings with overloaded constructors for such reasons. The sc.nextLine(); command is to send the scanner to the next line, correct?

17

Scanner.nextLine() reads a line from the standard input [ part of java.util package]
Integer.parseInt() converts a String to Integer [part of java.io package]
So,

int t=Integer.parseInt(sc.nextLine());

what this does is takes a full line stores it in a temporary String and immediately converts it into Integer

In general, we avoid using Scanner.nextInt() coz it reads an Integer one by one in a line…
So this would fail when we have multiple line inputs like -
1
2
0 1

One more thing, there is another way to input space seperated Integers on the same line

1 Like
18

Helpfull link

have a look GeeksForgeeks solution for this Question

1 Like
19

Thanks, i didn’t know about that lib

20

Are you referring to

 BufferReader br = new BufferReader( new InputStreamReader (System.in));