Hi! Here We Will dicuss about various programming challenges using C++ Language

Hey there!!! Let's begin our journey with a very simple problem. You are given an array and you need to sort it. Try yourself. I will be posting different approaches to tackle it.

Well there, sorting is an important tool to solve many problems. You will never be asked to sort an array in any competitive programming contest but sometimes you might have to sort an array as per requirements. So , you need to master the art of sorting an array correctly and quickly.
Some of the popular sorting algorithms are:
1) Bubble sort - https://www.geeksforgeeks.org/bubble-sort
2) Selection sort - https://www.geeksforgeeks.org/selection-sort
3) Insertion sort - https://www.geeksforgeeks.org/insertion-sort
4) Quick Sort - https://www.geeksforgeeks.org/quick-sort
5)Merge sort - https://www.geeksforgeeks.org/merge-sort
6)Count sort - https://www.geeksforgeeks.org/counting-sort
Of these sortng algorithms, Quick sort and Merge sort is more used as time taken by these algorithm is quite less than compared to bubble sort, insertion sort or selection sort. So it is recommended to use one of the Merge or Quick sort.
BUT WAIT!!!!! You surely don't want to write such a huge code during an ongoing competition. There is an easy way...........
Use the in-built sorting function of C++. It's just the matter of a line now!!!!
The prototype of the function is:
sort(start address, end address)
Eg: Suppose you have to sort an array A[n]. Then you just have to simply write
sort(A , A+n ) ;
and there you go you have a sorted array with very few efforts.
Remember to include "bits/stdc++.h" header file at the begining of you code.
I will be posting more on this sorting function as soon as possible.
AND HAA....here is the solution of the problem given:
https://www.codechef.com/viewsolution/23726104
Try to submit by yourself!!!!!!!!!

We have seen that the sort function of c++ sorts the array in increasing order by default, but what if we want to sort the array in decreasing order? We can simply do it by just modifying the function call statement. We just need to give an extra parameter during calling.
The syntax of the sort function will be:
sort (arr , arr+n , greater<int>());
A program which sorts an array in decreasing order is given here - https://pastebin.com/9zWH71Mz

Further more, we can use this sorting function to sort a structure according to one of its member element.
Here is an example of that - https://pastebin.com/LzYqHBVJ
In this example we use function named "func" to compare two elements. Basically the sort function passes two elements to the func function and if it gets 1 in return then first element is placed before the second element. And if 0 is returned then second element is placed before the first element. In this way we can sort a structure according to our need.

A prime number is a whole number greater than 1, which is only divisible by 1 and itself. First few prime numbers are : 2 3 5 7 11 13 17 19 23 …..

In many programming problems we have to check prime numbers efficiently. One of efficeient algorithms to find prime numbers is Seive of Eratosthenes. Check it out at GEEKS FOR GEEKS.

https://www.geeksforgeeks.org/sieve-of-eratosthenes/


For any query you can ask me
@saranyanaharoy


Thanks for joining our channel. 😄😄😄😄😄

Hello coding enthusiasts !!!!! This time we are upto something very interesting. It's PREFIX ARRAY!!!!! Prefix array is an important tool in competitive programming and it is something which every beginners should know. It comes under the category of basic dynamic programming and it reduces the repeated calculation process. Here is an excellent post on prefix array which will definitely help you to grab it in an easy way -
https://codeforces.com/blog/rash42
Though you may not get a direct problem which will ask you to create a prefix array, but sometimes you will have to use it in some other problem to reduce repeated calculations. So make yourself prepared for it.
Happy coding!!!

Well, many times you have uploaded a code and got different errors. Well it's ok.... it's a part of the learning process. Today I am going to discuss different types of errors we generally face with online judges.
1. Runtime Error- This mainly occurs if you try to access a memory location which is not allocated. For example if you initialize an array arr[5] and try to access arr[10] then you will get RE. You should always check whether the array location you are going to access is valid or not.
Even accessing a memory location suh as: arr[-1] will also give a RE. So also check the lower bound while accessing the array elements in reverse order.
2. Wrong Answer- The output of your code doesnot match with the correct answer. Well mostly it is the corner cases in which the code fails, so try to make some corner test cases by yourself and see whether your code passes it. There may be a possible buffer overflow so use long long int instead of int and watch carefully the given constraints.
3. Time Limit Exceeded (TLE)- Well nothing much to do in this one except brainstorming . You need to think of another algorithm to make it work.
4. Memory Limit Exceeded- This happens when you try to use more memory than the allotted memory. Probably you are declaring too big 2D array!!! Try to use different containers or data structure but it would be far better if you think of some different Algo.

You can get some silly errors which coders ofte make and how to handle it wisely in this article -
https://codeforces.com/blog/entry/67417

Happy Coding!!!

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

Hello Everyone!!!
It is time to face some interesting problems.
Are you excited😄😄😄😄

Our 1st problem is from codechef


PROBLEM LINK:
ONE KING

DIFFICULTY:
EASY-MEDIUM

PROBLEM:
Given N (≤100000) intervals [Ai , Bi], one such interval can be deleted by placing a bomb at x if Ai ≤ x ≤ Bi. Find minimum number of bombs required to delete all intervals.




SOLUTION:
EXPLANATION
CODE:
code

NOTE: Above idea is implemented using C++. Some C++ template classes from STL(Standard Template Library) are used. (STL). Specifically vector and pair are used in the solution code.

vector
pair
sorting vector of pairs


#oneking #codechef

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!!

Question: Given an Array of objects, you have to determine whether it has a majority element or not. A majority element is any element in the array which is present more than n/2 times in the array. Here equality expression holds but inequility expression doesnot holds, means A[i]==A[j] or A[i] != A[j] can be evaluated but A[i]<A[j] or A[i]>A[j] are meaningless and cannot be evaluated. Device an O(n) algorithm that returns the majority element or say no majority element exists.




Solution: Idea is to pair up the elements arbitrarily to get ceil(n/2) pairs. In each pair if the two elements are different we discard both of them. If they are same only one of them is kept. After the proposed procedure, there are atmost ceil(n/2) elements left and if A has a majority element, then this new array of remaining elements will have the same majority element. We then recursively call the same procedure on this new array.
Lets say m be the majority element we get once we apply the algorithm, now it is mandatory to check if m is indeed a majority element of the array. This can be done by a GetFrequency() call followed by a check whether the frequency of m in A[1...n] is greater than n/2 .


Below is the pseudo code:

procedure Check(A[1...n])
Input: Array A of objects
Output: Majority element of A
m = GetMajorityElementLinear(A[1...n])
freq = GetFrequency(A[1...n],m)
if freq >floor(n/2) + 1: 
    return m
else 
    return NO-MAJORITY-ELEMENT



procedure GetMajorityElementLinear(A[1...n])
Input: Array A of objects
Output: Majority element of A
if n==1:
    return A[1]
if n == 2:
    if A[1] == A[2]:
        return A[1]
    else 
        return NO-MAJORITY-ELEMENT
Create a temporary array temp
for i = 1 to n:
    if A[i] == A[i+1]:
        Insert A[i] into temp
    i = i+1
return GetMajorityElementLinear(temp)



Procedure GetFrequency(A[1,2.....n],m)
Input: Array A of object and an object m whose frequency is to be counted.
Output: Frequency of m.
c=0
for i=1 to n:
    if A[i]==m:
        c=c+1
return c

Recurrence relation for the algorithm is given as follows:
T(n) = T(n/2) + O(n).
As we can see the processing of array in the recursive function GetMajorityElementLinear() is done in O(n) time. Complexity of the function GetMajorityElementLinear() is O(n). Check() is also O(n). Therefore the whole algorithm is linear in terms of n.



Happy Coding!!!

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example Input:
[-2,1,-3,4,-1,2,1,-5,4],
Example Output: 6
Explanation:
[4,-1,2,1] has the largest sum = 6.

Hint : can be solved in O(N)
*Read Solution* : http://codingclub.tech/event/solution-max-subarray-sum

Hello Everyone!!

Yet Another Number Game Problem Code: NUMGAME
Alice and Bob play the following game. They choose a number N to play with. The rules are as follows :
1) Alice plays first, and the two players alternate.
2) In his/her turn, a player can subtract from N any proper divisor (not equal to N) of N. The number thus obtained is the new N.
3) The person who cannot make a move in his/her turn loses the game.

Assuming both play optimally, who wins the game ?

Input : The first line contains the number of test cases T. Each of the next T lines contains an integer N.
Output : Output T lines, one for each test case, containing "ALICE" if Alice wins the game, or "BOB" otherwise.

Sample Input :
2
1
2

Sample Output :
BOB
ALICE

Constraints :
1 <= T <= 10000
1 <= N <= 1000000000

Note : For the first test case, Alice cannot make any move and hence Bob wins the game. For the second test case, Alice subtracts 1 from N. Now, Bob cannot make a move and loses the game.

Can you solve ?
PROBLEM

Editorial for Solution:
EDITORIAL


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

Hello Everyone!!

Find the middle element of a linked list

Naive solution:
1. A simple way to determine the middle node would be
to fully pass through all nodes in the linked list
and count how many elements there are in total.
2. Then traverse the linked list again this time
stopping at the total/2 node.

For example,
the first time you traverse the linked list your program determines there are 10 nodes,
then the second pass through the linked list you stop at the 5th node,
which is the middle node.


This is a possible solution,
but there is a faster way.
Can you find it out ?

Read Optimal and Full Solution
SOLUTION


Happy Learning

Problem 1: You have n lists, each consisting of m integers sorted in ascending order. Merging these lists into a single sorted list will take time:

(a) O(nm log m) (b) O(mn log n)
(c) O(m + n) (d) O(mn)


Problem 2: A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Let G be a simple graph on 8 vertices such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex of degree 4, a vertex of degree 5, a vertex of degree 6 and a vertex of degree 7. Which of the following can be the degree of the last vertex?

(a) 3 (b) 0
(c) 5 (d) 4


Problem 3: When a user submits a query, a search engine does the following. For every webpage that has been visited by the search engine, it computes a score indicating how relevant that page is to the query. Finally, it reports the pages with the top k scores on the screen, for a number k specified by the user. A good data structure for accumulating the scores and ranking them is:

(a) a queue (b) a heap
(c) a stack (d) a binary search tree


Problem 4: A complete graph on n vertices is an undirected graph in which every pair of distinct vertices is connected by an edge. A simple path in a graph is one in which no vertex is repeated. Let G be a complete graph on 10 vertices. Let u, v, w be three distinct vertices in G. How many simple paths are there from u to v going through w?


Solutions:
Answer 1: b) O(mn log n)

We can merge two sorted lists of size k and l in time
O(k +l). We begin by merging the lists in pairs to generate n/2 lists of size 2m each. To generate a list of size 2m we require O(m+m) time. Therefore to generate n/2 list the time required will be O(mn). If we repeat this, we get n/4 lists of size 4m each, again in total time O(mn). Thus, in O(log n) rounds, we converge to a single sorted list. Each round takes time O(mn), so the total time is O(mn log n).
Another strategy to achieve complexity O(mn log n) is to build a min-heap of size n, consisting the first element in each of the n lists. We then extract the minimum element from the heap to the output and replace it in the heap with the next element from the list from which the minimum came. Thus, it takes time O(log n) to generate each element in the output and there are O(mn) output elements in all, so the overall time
is O(mn log n).


Answer 2: d) 4

The number of odd degree vertices in any graph is even. Since we already have four
vertices of odd degree, the degree of the last vertex cannot be 3 or 5. It cannot be 0 either, since there is one vertex with degree 7, which means that it is a neighbour to all the other vertices, which implies that there is no isolated vertex in the graph. Thus the only possible degree of the last vertex is 4.


Answer 3: b) a heap

Let n be the number of pages visited by the search engine at the time a query is submitted. Assume that it takes constant time to compute the relevance score for each page w.r.t. a query. Then it takes O(n) time to compute the relevance scores, a further O(n) time to build a heap of n relevance scores, and O(k·log n) time for k delete-max operations to return the top k scores.

Answer 4: For every path from u to v, w is always present. Now, the no of nodes from the remaining 7 nodes (10 nodes -{u,v,w}) can be choosen in 7Ci ways and for each of the choosen i vertices, these nodes can be travelled in (i+1)! ways ( i+1 because we are including the w vertex also, along with the i vertices). Thus the total no of ways are:

=(7C0).(1!) + (7C1).(2!) + (7C2).(3!) + (7C3).(4!) + (7C4).(5!) + (7C5).(6!) + (7C6).(7!) + (7C7).(8!)

=95901.



Happy Coding!!!!