-
Notifications
You must be signed in to change notification settings - Fork 1
/
c++ Refreshment !
220 lines (158 loc) · 8.8 KB
/
c++ Refreshment !
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
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]);
}
}