Count of digits in factorial

 To count the digits in a factorial we must seek some optimization as you might also understand that getting all the product and storing them could lead to wastage of storage.

So what to do?

Lets see this :

As we can see by doing this we can get count of numbers in the range, like 

1-9 = 1 digit

10-99 = 2 digit

100-999 = 3 digit

and so on.

we got the formula = floor[log(x)] + 1

but wait we need for factorial not a single digit right?

like factorial of  5! = 1 * 2 * 3 * 4 * 5

                              = 120 
and we need to check for 120 not 1,2,3,4,5. so what to do?

well 5! can be written as 1 * 2 * 3 * 4 * 5 so no worries. 

so lets put that in the equation.

floor[log(x)] = floor[log(120)] = floor[log(1*2*3*4*5)]

Now from the log formula we know we can add these simply. 

floor[ log(1) + log(2) + log(3) + log(4) + log(5) ] + 1

There you have it!!!

Now code :

Prime Optimized

 Know if the number is Prime Or Not Most Optimized Way.

we know by dividing till root N but that's not the best approach. 
We can move even further beyond by this technique to increase its efficiency by 3 times.

first we put checks of divisible by 2 and 3
and if not then further go on iterating by increasing the iterator by 6. Why? bcz 2 and 3 would cover up for all the numbers in between.
and another condition inside checking for number divided by iterator+2 for cases like 7,13, etc

Code :

LCM optimized

 Optimized solution to find LCM

We can use the formula :
A * B = GCD(A,B) * LCM(A,B)
(simple pair hai ye....)
As,
LCM(A,B) = (A*B) / GCD(A,B)

What is GCD?
=>  Here

Code :

GCD/HCF optimized

How to calculate GCD/HCF with optimization.

Step 1 : Calculate Remainder between A and B.

Step 2 : Change A with B and B with remainder obtained

Step 3 : Do this recursively till we get B as 0

 

Note : A > B, if its not the case then change B and A.

Code :

Trailing zeros of factorial

In this post i am going to explain the problem and how to solve it.

See the trailing zeros of a factorial means when we get a factorial of a number then the resultant might end with couple of zeros.
for example :
5! = 5 * 4 * 3 * 2 * 1 

= 120

 As we can see here in the number 120 we got a 0 likewise in other factorials we might get many more zeros so now the task is to identify those numbers which ends with zeros.

So to do this we must see the prime factorization of the resultant numbers meaning prime factorization of 120 = 2 * 2 * 2 * 3 * 5

And now if we see it clearly then the pattern which is making the trailing zeros happen is the 5*2 pair in the prime factorization as it would make 10 and multiplying any number with 10 would result in extra 0 to the end.

Now things to consider :
we can see there are more numbers of 2 than 5 which would be the general case for all numbers so we can simply count the number of 5's in the prime factorization of the number to get the count of number of zeros.

But there's a small catch to this logic, which is that there are numbers multiple of 5 which could be there in the prime factorization and since it's an already multiple of 5 so it would have an extra 5 inside it which we need to count.
for example : 25 or 125 so 
25 = 5 * 5 
and 
125 = 5 * 5 * 5

so as per our above logic we were counting all the 5's and also that we wont be calculating all the product and then prime factorization for real as we could get all the 5 at the end bcz it would be computationally expensive, right!!

So what we can do is divide the given number with all the multiple of 5 below that number meaning :

Example : 
5! = 120 = 5/5 = 1 

Similarly,
25/5 = 5
25/25 = 1

therefore 5+1 = 6 zeros

So the code should be :

 

Saving 2 elements at single index

 Yes we can save two numbers at one place by using simple mathematical formula.

The formula : 

dividend=divisor*quotient+remainder

Rotate an array in O(n)

Step 1 :
Reverse the first k elements.

Step 2:

Reverse the k+1 to n-1 elements.

Step 3:

Reverse the whole array.

Prefect!!!

Example :

arr=[1,2,3,4,5] , k=2

expected output : [3,4,5,1,2]

step 1:

[2,1,3,4,5]

step 2:

[2,1,5,4,3]

step 3:

[3,4,5,1,2]

Got it!