c++ Refreshment !

n C++, two most common choices to do is

iosteams - cin / cout (NEW)
stdio - scanf / printf (C style)
Though it seems inconsequential, handling I/O correctly can make your solution milliseconds or even a few seconds. This becomes relevant when the input is huge (for example, reading 10^610
​6
​​  integers).

Before moving on to I/O optimization, let’s quickly see how to use each I/O function.

Stdio #
Include statement: #include <cstdio>

scanf and printf need to know the type of the variable you are reading/printing, denoted by using a format specifier (%).

Here are the most common ones, for a complete list you can go here

scanf("%d", &x); // read int
scanf("%lld", &x); // read long long int
scanf("%s", &s); // read string
scanf("%f", &d); // read float
Similarly,

printf("%d", &x); // print int
printf("%lld", &x); // print long long int
printf("%s", &s); // print string
printf("%f", &d); // print float
Two space separated integers can also be read in a single scanf statement

scanf("%d %d", &a, &b);

////////////////////////////////////////////////////////


Is my solution going to run in time? #
The actual answer will depend on a number of factors like hidden constants, allowed execution time, and the server where the code is executed.

Nevertheless, below is a general rule of thumb to determine whether your solution is going to run in time, given that the time constraint is only a few seconds:

                              N                                                Acceptable
                      10^7                                                      O(N)

 	          10^6                                                          O(N*logN)
       
                 10^5                                               	O(N*log^2N) ,                                                                 (N*\sqrt{N})O(N∗√oN)
        
               10^4                                                              O(N^2)
etc ............

#PRIME FACTORS FINDING  -O(sqrt(n)) approach

void print_prime_factors(int N){
  for (int i = 2; i * i <= N; i++) {
    if (N%i == 0){
      cout << i << " ";
      while (N%i == 0) 
        N /= i;
    }
  }
  if (N > 1)
    cout << N << " ";
  cout << "\n";
}

#ARRAYS  VS VECTORS  : Many times, you need a structure like an array that is dynamic in size. Vectors are dynamic arrays. Vectors, similar to an array, have contiguous memory allocation 
so that random access is O(1)O(1) for vectors as well. One way to implement vectors using an array is to copy the array to a new array of double the size every time the first array is full.
As discussed in the complexity analysis chapter, the amortized time complexity is O(1) for inserting elements in such a case.

#VECTORS : operations
vector<int> v; // new empty vector !
vecotr<int> v(5); // new vector of size 5
vecotr<boolean> v(5, true); // new vector of size 5 with all values initialized to true
 
v.size(); // get size
v[i]; // access ith element
 
v.push_back(x); // insert x at end of vector
v.pop_back(x); // delete last element
 
v.begin(); // get iterator to beginning
v.end(); // get iterator to end (theoretically, the element after the last element)
 
v.erase(v.begin() + 4); //delete 4th element
 
sort(v.begin(), v.end()) //sort vector
reverse(v.begin(), v.end()) // reverse the vector


---------> Accumulate : used for finding the sum of array or vector wihout any func : 
int sum = 0 ;
accumulate(arr.begin() , arr.end() , sum ) ; cout<<sum<<endl;
similary ....accumulate(arr , arr+n , sum ) ; cout<<sum<<endl;


Q.Given an array AA of NN integers. Answer QQ queries of the type (l, r)(l,r) - reverse the subarray A[l...r]A[l...r]. Print the array after each query.
Input format The first line contains two integers NN and QQ (1 \leq N, Q \leq 10^3)(1≤N,Q≤10 ).The second line contains NN space-separated 
integers representing the array A[]A[] (1 \leq A[i] \leq 10^6)(1≤A[i]≤10).

for(int i = 0; i < Q; i++) {
    int l, r;
    cin >> l >> r;
    l --; r --; // covert to 0-based index

    for(int p1 = l, p2 = r; p1 < p2; p1++, p2--){
      swap(A[p1], A[p2]);
    }
  }
  
  Q.SubArray sum problem ! ->Given an array, AA, of NN integers, answer QQ queries of the type (l, r)(l,r) - sum of the elements in the 
  subarray A[l...r]A[l...r]. Print the sum for each query. Next, QQ lines each contains pair of integers ll and rr (1 \leq l \leq r \leq N)(1≤l≤r≤N)
  
  Optimization #
First, let’s discuss what the prefix sum array is.

The prefix sum array sum[]sum[] of an array A[]A[] is defined as

sum[i] = \sum_{k=1}^{i} A[k]sum[i](i,A[k] =∑k=1

or, iith element of sum[]sum[] is sum of first ii elements of A[]A[]

We can use the prefix sum array to find the sum of a subarray in O(1)O(1) time.

sum[i...j] = A[i] + A[i+1] + ... + A[j]sum[i...j]=A[i]+A[i+1]+...+A[j]

== (A[1] + A[2] + ... +A[j]) - (A[1] + A[2] + ... +A[i-1])(A[1]+A[2]+...+A[j])−(A[1]+A[2]+...+A[i−1])

== sum[j] - sum[i-1]sum[j]−sum[i−1]

From preprocessing to computing the sum[]sum[] array takes O(N)O(N) time. Each query is just O(1)O(1).

So the total time complexity is O(N + Q). otherwise time complexity is O(n*Q) ;

#Sieve of Eratosthenes #
The Sieve of Eratosthenes is a simple algorithm to generate all primes to generate all primes from 11 to NN in O(N*log(logN))O(N∗log(logN)).
Steps:
Create a list of all numbers from 22 to NN. Initially, all numbers are unmarked.
Starting from p=2p=2, we will mark all multiples of 22 less than or equal to NN. These numbers are definitely not prime since 22 divides them.
Move to the next unmarked number, i.e., p = 3p=3. Mark all its multiples.
Stop if p>\sqrt{N}p>√
N
Each unmarked number that we visit is a prime because all non-primes will be marked by one of its factors before we reach this number.

We can use a Boolean array of size NN to distinguish between marked and unmarked numbers.

Let’s understand the process better using the illustration below for N = 30. We will stop after we reach :ceil(√3 0) i.e 66

 vector<bool> is_prime(N + 1, true); // size is N+1 so we can access is_prime[N]
  
  for (int i = 2; i * i <= N; i++) {
    if (is_prime[i]) {
      for (int j = i + i; j <= N; j += i)
        is_prime[j] = false;
    }
  }
  Given two integers, NN and MM, print all primes between NN and MM (both inclusive).
  vector<int> is_prime(M-N+1, true);

  for (int i = 2; i * i <= M ; i++) {
    int start = (((N - 1) / i) + 1) * i;
    for (int j = start; j <= M ; j+= i) {
      if (j >= N && j <= M) 
        is_prime[j - N] = false;
    }
  }
  
  
  
  
 #STRINGS IN c++ !
Converting Strings to Numbers in C/C++ : stoi() : The stoi() function takes a string as an argument and returns its value. Following is a simple implementation:
     ]string str1 = "45"; 
    string str2 = "3.14159"; 
    int myint1 = stoi(str1); 
    int myint2 = stoi(str2); 
    cout<<myint1<<endl ;stoi("45") is 45
                        stoi("3.14159") is 3
                        
     and for int to char or in string us to_string(x) ;

#Sorting Methods : 

1.selection sort !
Selection sort #
Maintain two parts of the array, sorted and unsorted parts. Starting with the sorted part being empty and the unsorted part being A[0..N-1]A[0..N−1], repeatedly find the smallest integer in the unsorted part and swap it to the end of the sorted part.

A small example will explain the process quickly. In this example, the unsorted part is bold.

Step 0: [6, 3, 5, 4, 1, 2]
Step 1: find minimum in A[0..5]A[0..5] and move to 0 -> [1, 3, 5, 4, 6, 2][1,3,5,4,6,2].
Step 2: find minimum in A[1..5]A[1..5] and move to 1 -> [1, 2, 5, 4, 6, 3][1,2,5,4,6,3].
Step 3: find minimum in A[2..5]A[2..5] and move to 2 -> [1, 2, 3, 4, 6, 5][1,2,3,4,6,5].

int N = 6;
  int arr[N] = {6, 3, 5, 4, 1, 2};

  for (int i = 0; i < N; i++) {
    int min_idx = i;
    for(int j = i + 1; j < N; j++) {
      if (arr[j] < arr[min_idx])
        min_idx = j;
    }
    swap(arr[i], arr[min_idx]);
  }

2.Bubble sort
For each element starting from the first, compare with the adjacent element and swap the two if they are in incorrect order, i.e., arr[i] > arr[i+1]. The first iteration places the largest element at arr[N-1]. The second iteration places the second largest at arr[N-2] and so on…

Initially:[6 3 5 4 1 2]
Iteration 1: [6 3 5 4 1 2] -> [3 6 5 4 1 2] -> [3 5 6 4 1 2] -> [3 5 4 6 1 2] -> [3 5 4 1 6 2] -> [3 5 4 1 2 6]
Iteration 2: [3 5 4 1 2 6] -> [3 5 4 1 2 6] -> [3 4 5 1 2 6] -> [3 4 1 5 2 6] -> [3 4 1 2 5 6]
Iteration 3: [3 4 1 2 5 6] -> [3 4 1 2 5 6] -> [3 1 4 2 5 6] -> [3 1 2 4 5 6]
For example, in the third iteration, we can stop after the first four elements because the previous two iterations will make sure the last two elements are larger than the first four elements.
int arr[6] = {6, 3, 5, 4, 1, 2};

  for (int i = 0; i < N; i++) {
    for(int j = 1; j < N - i; j++) { // skip comparing with last i elements
      if (arr[j] < arr[j-1])
        swap(arr[j], arr[j-1]);
    }
  }