Every C/C++ program is said to have a main() function, but have you ever wondered is it possible to write a C/C++ program without main() function??
It is possible to write a C/C++ program without a main() function. Check out how -https://qr.ae/TWGwGa

Hey there!!! Whenever we want to get the maximum value between two variables (suppose we want to store the largest value among variable1 and variable2 into variable3) we use the if else statement. But we can do it in another simple way without much effort by using max() function. The prototype is:
variable3=max(variable1,variable2);
Similarly, we can use the min() function to get the minimum among two variables.The prototype of the function is:
variable3=min(variable1,variable2);

Again, if we want to get the maximum value within an array we could do it very easily, we just need to call the *max_element() function. The prototype is:
variable_name=*max_element(arr,arr+n);
where arr[n] is an array of size n.
In the same way we could easily get the minium element from an array by using *min_element() function. The protype is:
variable_name=*min(arr,arr+n);
Here arr[n] is the array of size n.

Note: Don't forget to write #include<bits/stdc++.h> in the begining of the code, because every functions is defined in this header file!!!!

Happy Coding!!!

Hello Everyone!!


Question: How many zeros are there in 100! (100 factorial)?

Ok, let’s look at how trailing zeros are formed . When a 5 and a 2 is contained in factors of a number a trailing 0 is formed.Now all we have to do is count number of 5's and 2's in the factors.

Let’s count the 5’s first. 5, 10, 15, 20, 25 and so on making a total of (100/5)=20. However there is more to this. Since 25, 50, 75 and 100 have two 5’s in each of them (25 = 5 * 5, 50 = 2 * 5 * 5, …), you have to count them twice.
So this makes the total (20+100/25)=24.

In formula point of view:
Number of 5's in 100!
= 100/5 + 100/25 + 100/125 + ... = 24 (Integer values only)

Moving on to count the number of 2’s. 2, 4, 6, 8, 10 and so on.
Total of

50 multiples of 2’s,

25 multiples of 4’s (count these once more),

12 multiples of 8’s (count these once more)

and so on…
The grand total comes out to

Number of 2’s = 100/2 + 100/4 + 100/8 + 100/16 + 100/32 + 100/64 + 100/128 + … = 97 (Integer values only)

Each pair of 2 and 5 will cause a trailing zero. Since we have only 24 5’s, we can only make 24 pairs of 2’s and 5’s thus the number of trailing zeros in 100 factorial is 24.






Now we can use the concept to find number of trailing 0's in N!(Where N is an positive integer). We only have to calculate number of 5's in the factors of N! as number of 2's are always greater than the number of 5's.

Pseudocode:

N=input
div=5
count=0
while(N/div!=0)
    count+=N/div;
    div=div*5
print count

CODE:
code



For any question feel free to contact me:
@saranyanaharoy

Happy Learning!!

Fast IO Optimization in C++

In competitive programming, it is important to optimize I/O methods as time limit of some problems is very strict.

You must have seen various problem statements saying: “Warning: Large I/O data, be careful with certain languages (though most should be OK if the algorithm is well designed)”. Key for such problems is to use Faster I/O techniques.

Lets say you have taken an input of 10^5 numbers, there are many methods for input/output

1. std::cin>>x;
std::cout<<x;

you can use std::cin and std::cout. How ever there are better methods

2.scanf("%d",&x);
printf ("%d",x);

scanf / printf are roughly thrice as fast as the cin/cout.

However, you can still use cin/cout and achieve the same speed as scanf/printf by including the following lines in your main function.

#include <bits/stdc++.h>
using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}

To know more about this read here.

3. FAST IO

void fastscan(int &x)
{
bool neg = false;
register int c;
x = 0;
c = getchar();
if(c == '-')
{
neg = true;
c = getchar();
}
for(;(c>47 && c<58);c=getchar()) x=(x<<1)+(x<<3)+c-48;
if(neg) x *=-1;
}

fastscan(x);

this is one of the fastest way to take an integer input from STDIN this is around 10 times faster than scanf() This is very useful in competetive programming.

Similiarly to print an integer, the following fastprint() function can be used.

void fastprint(int n)
{
if (n == 0)
{
putchar('0');
putchar('\n');
}
else if (n == -1)
{
putchar('-');
putchar('1');
putchar('\n');
}
else
{
int neg=0;
char buf[20];
if(n<0){
neg=1;
n=-n;
}
buf[10] = '\n';
int i = 9;
while (n)
{
buf[i--] = n % 10 + '0';
n /= 10;
}
if(neg)buf[i--]='-';
while (buf[i] != '\n')
putchar(buf[++i]);
}
}

fastprint(n);



We can test our input and output methods on the problem : PROBLEM

Solution:
CODE

For any doubt or correction feel free to contact me:
@saranyanaharoy

Happy Learning

Sliding Window Maximum (Maximum of all subarrays of size k)

Given an array and an integer K, find the maximum for each and every contiguous subarray of size k.

Examples:
Input: arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}, K = 3
Output: 3 3 4 5 5 5 6

Input: arr[] = {8, 5, 10, 7, 9, 4, 15, 12, 90, 13}, K = 4
Output: 10 10 10 15 15 90 90

We have discussed the brute force and optimal solutions in a previous post.
In this post we focus on the O(n) solution and analyse time complexity of the solution.



Explanation:
We create a Deque Q of size k and maintain the following conditions:
1. Q contains only the useful elements of current window.
2. Q contains the elements in descending order.

Now what are useful elements?

Suppose the array is
{10,5,4,3,1,7,6} and k=6

We start traversing input array from index 0 and as we reach index 4 our deque Q contains
{10,5,4,3,1} as all the elements are useful.
Now after we read 7 at index 5 the elements 5,4,3,1 become useless here.
For any window afterwards if it contains 5,it will also contain 7.As 7 is greater than 5 and we are looking for maximum , 5 is useless.Similiarly 4,3,1 are also useless.
So Q contains {10,7}.
Now our window size is 6. For the next element in the array 10 is outside of the window.So We print 10 and pop it from the Q.
Q contains {7,6}.
We process all array elements one by one and maintain Q to contain useful elements of current window and these useful elements are maintained in descending order. The element at front of the Q is the largest of current window.



Pseudocode:
n=size of array
a=array
a=input
Q=deque //We will store the indices of useful elements in the deque
for i=0 to k-1:
while(!Q.empty() and a[i]>=a[Q.rear()]):
Q.pop_back()
Q.push_back(i)
for i=k to n:
print a[Q.front()]
while(!Q.empty() and Q.front()<=i-k):
Q.pop_front()
while(!Q.empty() and a[i]>=a[Q.rear()]):
Q.pop_back()
Q.push_back(i)
print a[Q.front()]



Time Complexity:
Suppose 1st k elements of input array are in descending order.So after passing through 1st k elements of input array deque contains k elements.
Let's say each of remaining (n-k) elements will be greater than half of elements present in deque.To insert (k+1)th element we have to make (k/2+1) comparisons and after insertion there will be(k/2) elements in the deque. To insert (k+2)th element we have to make (k/4+1) comparisons and after insertion there will be (k/4) elements in the deque.So to insert all the elements of input array in the deque total number of comparisons will be:
k+((k/2+1)+(k/4+1)+(k/8+1)+......(n-k) terms....)
= (k + k/2 + k/4 + ....(n-k+1) terms.....) +(n-k)
= ( k * (1 - (1/2)^ (n-k+1)) / (1-1/2) ) +(n-k)
= 2 * k * (2 ^ (n-k+1)-1) / (2^(n-k+1)) +(n-k)
≅ 2 * k *(2^(n-k+1)) / (2^(n-k+1)) +(n-k)
≅ 2*k + n - k
≅ n + k
So time complexity of above algorithm is O(n+k) i.e O(n) as (k<=n).



Code:
CODE


For any doubt or correction feel free to contact me:
@saranyanaharoy

Happy Learning

Range update query
Consider an array A[] of integers and following two types of queries.

update(l, r, x) : l is left index, r is right index and x is value to be added i.e add x to all values from A[l] to A[r] (both inclusive).
printArray() : Prints the current modified array.


Solution:

Using Prefix Array:
Take an array pref of same size as input array.Initialize it with 0.

1.Upadate(l,r,x):
Add x to pref[l] and substract it from pref[r+1]
i.e we do pref[l]+=x , pref[r+1]-=x

2.PrintArray():
Take prefix sum of pref array i.e
for i=1 to n-1
pref[i]=pref[i]+pref[i-1]
Now, for all elements of input array
do A[i]=A[i]+pref[i] and print them

Here update range operation is performed in O(1).
printArray is performed in O(n).


Pseudocode:

n=size of array
A=array
pref=array
initialize pref with 0
A=input

update(l,r,x):
  pref[l]+=x
  if(r+1<n)
    pref[r+1]-=x

printArray():
  for i=1 to n-1
    pref[i]=pref[i]+pref[i-1]
  for i=0 to n-1
    A[i]=A[i]+pref[i]
  for i=0 to n-1
    print A[i]
    print " "
  print "\n"

Code:
CODE



Using Difference Array:
Difference array D[i] of a given array A[i] is defined as D[i] = A[i]-A[i-1] (for 0 < i < N ) and D[0] = A[0]

1.Upadate(l,r,x):
Add x to D[l] and substract it from D[r+1]
i.e we do D[l]+=x , D[r+1]-=x

2.printArray():
Do A[0] = D[0] and print it.
For rest of the elements, do A[i] = A[i-1] + D[i] and print them.

update range operation is performed in O(1).
printArray is performed in O(n).

Pseudocode:
n=size of array
A=array
D=array
A=input

D[0]=A[0]
for i=1 to n-1
D[i]=A[i]-A[i-1]


update(l,r,x):
D[l]+=x
if(r+1<n)
D[r+1]-=x

printArray():
A[0]=D[0]
for i=1 to n-1
A[i]=A[i-1]+D[i]
for i=0 to n-1
print A[i]
print " "
print "\n"

Code:
CODE


For any doubt or correction feel free to contact me:
@saranyanaharoy

Happy Learning

Explanation:
Example case 1: When Josh is at the position P=4, the soldiers' initial powers in clockwise order around the circle, starting with soldier 1, are [12,34,45,D,5] (D denotes Josh). Then, the following happens:
The soldier with power 12 attacks the soldier with power 34 and kills him.
The soldier with power 45 attacks Josh, who defends. The living soldiers' powers are now [12,45,D−45,5] and Josh is the attacking soldier.
Josh does not attack, so the soldier to his right (with power 5) becomes the attacking soldier. He attacks the soldier with power 12 and kills him.
The soldier with power 45 attacks Josh again and Josh defends again.
The soldier with power 5 attacks the soldier with power 45 and kills him.
Now, two soldiers are left: Josh (with a shield with defense power D−90) and the soldier with a sword with power 5. Each of them is attacked with firepower F=10, so the power of Josh's shield drops to D−100 and the other soldier dies.
If Josh survives, his shield's initial power D should be at least 45+45+10=100. For all other positions P, Josh cannot survive.

Example case 2: Regardless of how large D is and which position Josh chooses, after Chefland's attack, a soldier of Bitland other than Josh will always survive. This soldier will then attack Josh until his shield breaks and he dies.




Solution:
EDITORIAL

Pseudocode:

int Damage(int n, int a[],int p)
  int s = (n-(p+1)) + ceil(p/2)
  int d = 0
  if(p%2 != 0)
    d = d + a[p]
  int last = s
  int step = 2
  while( last != 1)
    if((last-1)%step==0)
      if(last<=(n-(p+1))
        d = d + a[last+p]
      else
        d = d + a[2*(k-n+p)+1]
    else
      last = ((last-1)-(last-1)%step)+1
    step = step*2
  return d

int n,f
n,f=input
n=n-1
int a[n+1]
a[0] = 0;
for i = 1 to n
    a[i]=input
int result[n]

initialize result with -1

for i=0 to n 
    if(a[i]<=f)
        result[i]=damage(n,a,i)
int count=0
for i=0 to n
     if(result[i]!=-1)
         count=count+1
if(count==0)
      print "impossible"
else
      int index=n+1
      int min_damage=INT_MAX
      for i = n to 0
           if(result[i] != -1 && result[i]<=min_damage)
                 index=i
                 min_damage=result[i]
      print "possible\n"
      print index+1
      print min_damage+f

Code:
CODE

For any doubt or correction feel free to contact me:
@saranyanaharoy

Happy Learning