International Islamic University Chittagong
Department of Computer Science & Engineering
Autumn - 2023
Course Code: CSE-2430
Course Title: Competitive Programming II
Jafrin Iqbal Chowdhury
Adjunct Lecturer, Dept. of CSE, IIUC
Max, Min Element in an array:
Frequency Count
Frequency count involves counting the occurrences of each element in an array
Frequency Count with Brute Force
int arr[100], freq[100];
int size, i, j, count;
scanf("%d", &size);
for(i=0; i<size; i++){
scanf("%d", &arr[i]);
freq[i] = -1;
}
for(i=0; i<size; i++){
count = 1;
for(j=i+1; j<size; j++){
/* If matches */
if(arr[i]==arr[j]){
count++;
/* Make sure not to count frequency of same element again */
freq[j] = 0;
}
}
/* If frequency of current element is not counted */
if(freq[i] != 0){
freq[i] = count;
}
}
for(i=0; i<size; i++){
if(freq[i] != 0){
printf("%d occurs %d times\n", arr[i], freq[i]);
}
}
Frequency Count with Frequency Array
vector<int> frequencyCount(const vector<int>& arr, int maxVal) {
vector<int> freq(maxVal + 1, 0);
for (int num : arr) {
freq[num]++;
}
return freq;
}
int main() {
vector<int> arr = {1, 2, 1, 3, 2, 4};
int maxVal = 4;
vector<int> freq = frequencyCount(arr, maxVal);
cout << "Frequency Array: ";
for (int num : freq) {
cout << num << " ";
}
cout << endl;
return 0;
}
Frequency Count with STL MAP
int arr[] = {3, 2, 4, 2, 5, 4, 3, 2, 4, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
map<int, int> frequencyMap;
for (int i= 0; i < n; i++) {
frequencyMap[arr[i]]++;
}
for (auto &entry : frequencyMap) {
cout << "Element " << [Link] << " appears " << [Link] << " times." <<
endl;
}
Compare Time Complexity
The brute force approach for frequency count has a time complexity of O(N^2) since it uses nested loops.
The frequency array approach and Map have a time complexity of O(N) since it iterates through
the array once.
Uva – 11577 (Letter Frequency)
Uva – 11577 (Letter Frequency)
Subarray: A subarray is a contiguous segment of elements within an array. It's a subset of the original array
that preserves the order of elements. In simpler terms, if you take some consecutive elements from an array,
that subset is called a subarray. A subarray is formed by selecting a range of elements from the original array,
maintaining their order as they appear in the original array. The elements within a subarray must be
consecutive and not [Link] are commonly used to perform range-based operations, such as
finding the sum, maximum, or minimum of a specific range of elements in an array.
int arr[] = {1, 2, 3, 4};
int size = sizeof(arr) / sizeof(arr[0]);
for (int start = 0; start < size; start++){
for (int end = start; end < size; end++){
vector<int> subarray;
for (int i = start; i <= end; i++){
subarray.push_back(arr[i]);
}
cout << "Subarray: ";
for (int num : subarray){
cout << num << " ";
}
cout << endl;
}
}
Subsequence: Subsequences are useful for problems where you need to find patterns or combinations
of elements in an array while maintaining their relative order.
void generateSubsequences(vector<int>& nums, vector<int>& current, int index){
if (index == [Link]()){
for (int num : current){
cout << num << " ";}
cout << endl;
return;
}
// Include the current element in the subsequence
current.push_back(nums[index]);
generateSubsequences(nums, current, index + 1);
// Exclude the current element from the subsequence
current.pop_back();
generateSubsequences(nums, current, index + 1);
}
int main(){
vector<int> nums = {1, 2, 3};
vector<int> current;
generateSubsequences(nums, current, 0);
}
Prefix Sum & 2D Grid – Study From Previous Material
Problems:
Frequency
1. [Link]
2. Uva 10062 - Tell me the frequencies!
3. Uva 10789 - Prime Frequency
4. Uva 499 - What's The Frequency, Kenneth?
Prefix Sum
1. [Link]
2. [Link]
3. [Link]
4. Uva 108 - Maximum Sum
SubArray
1. [Link]
Subsequence
1. [Link]
2D Array
1. [Link]
12
13
String
A string is a class that defines objects that be represented as a
stream of characters.
14
Input and output using cin: Input and output using getline:
#include <iostream> #include <iostream>
#include <string> #include <string>
int main() { int main() {
string input; string input;
cout << "Enter a string: "; cout << "Enter a string: ";
cin >> input; getline(cin,input);
cout << "You entered: " << input << endl; cout << "You entered: " << input <<endl;
return 0; return 0;
} }
15
String Built-in Functions:
Functions Code
Length
Accessing Characters
Concatenation
Substring
Find
Replace
Compare
Conversion to C-Style String
Empty Check
Clear
16
String Built-in Functions:
Functions Code
Erase
Insert
Find Last Occurrence
Substring Copy
Transform to Uppercase/Lowercase
String Comparison (Case Insensitive)
Find First Not Of
Find Last Not Of
17
Palindrome
function isPalindrome(str)
left = 0
right = length(str) - 1
while left < right do
if str[left] ≠ str[right] then
return false
end if
left = left + 1
right = right - 1
end while
return true
end function
18
Different tricks of creating a palindrome
Even-Length Palindromes:
Odd-Length Palindromes:
19
Lexicographical Analysis
Using Bruteforce:
bool isSmaller(string a, string b) {
int len = min([Link](), [Link]());
for (int i = 0; i < len; ++i) {
if (a[i] < b[i]) {return true;}
else if (a[i] > b[i]) {return false;}
}
return [Link]() < [Link]();
}
void lexicographicalBubbleSort(vector<string>words) {
int n = [Link]();
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < n - i - 1; ++j) {
if (!isSmaller(words[j], words[j + 1])) {
swap(words[j], words[j + 1]);}}}}
int main() {
vector<string> words = {"apple", "banana", "grape", "cherry"};
lexicographicalBubbleSort(words);
for (string& word : words) {cout << word << endl;}
20
}
Using STL:
int main() {
vector<string> words = {"apple", "banana", "grape", "cherry"};
sort([Link](), [Link]()); // Sort lexicographically
for (string word : words) {
cout << word << endl;
}
21
Using Custom Comparator:
bool customComparator(string a, string b) {
return [Link]() < [Link](); // For example, sort by length
}
int main() {
vector<string> words = {"apple", "banana", "grape", "cherry"};
sort([Link](), [Link](), customComparator);
for (string word : words) {
cout << word << endl;
}
22
A stringstream associates a string object with a stream allowing you to read from the string as
if it were a stream (like cin). To use stringstream, we need to include sstream header file. The
stringstream class is extremely useful in parsing input.
Basic methods are:
clear()- To clear the stream.
str()- To get and set string object whose content is present in the stream.
operator <<- Add a string to the stringstream object.
operator >>- Read something from the stringstream object.
23
// Word Count
#include <iostream>
#include <sstream>
#include<string>
using namespace std;
int countWords(string str){
stringstream s(str);
string word;
int count = 0;
while (s >> word) {
cout<<word<<endl;
count++;
}
return count;
}
int main(){
string s = "geeks for geeks geeks contribution placements";
cout << " Number of words are: " << countWords(s);
return 0;
}
Time complexity: O(n*log(n)).
Auxiliary space: O(n).
24
// Decimal to hexadecimal // converting number to string
#include <bits/stdc++.h>
using namespace std;
#include <iostream>
#include <sstream>
int main()
{ int main() {
int i = 942;
stringstream ss; int num = 123;
ss << hex << i; string numStr;
string res = [Link](); stringstream ss;
cout << "0x" << res << endl;
// this will print 0x3ae
ss << num;
return 0; numStr = [Link]();
} cout << "Converted string: " << numStr << endl;
Time complexity: O(1) return 0;
Auxiliary space: O(1). }
25
A substring is a contiguous sequence of characters extracted from a larger string. It represents a smaller portion
of the original string. In other words, a substring is formed by selecting a range of characters from a given string,
maintaining their order as they appear in the original string.
If you carefully see, you will notice that the number of substrings of a string of length N is equal to (N*(N+1))/2.
(This expression does not include the empty string as a substring).
Substring using STL:
#include <iostream>
#include <string>
int main() {
string str="We think in generalities, but we live in details.";
string str2 = [Link] (3,5); // "think"
size_t pos = [Link]("live"); // position of "live" in str
string str3 = [Link] (pos); // get from "live" to the end
cout << str2 << ' ' << str3 << '\n';
return 0;
} 26
Problem Statement:
Given a string, find the longest palindrome substring within it.
Input: A single line containing a string of lowercase alphabets (length ≤ 1000).
Output: Print the longest palindrome substring
Sample Test Case:
Input:
babad
Output:
bab
27
function longestPalindromeSubstring(string s)
n = length(s)
longestSubstr = ""
for i = 0 to n - 1
for j = i to n - 1
currentSubstr = [Link](i, j - i + 1)
if isPalindrome(currentSubstr) and length(currentSubstr) > length(longestSubstr)
longestSubstr = currentSubstr
end if
end for
end for
return longestSubstr
end function
28
Substring Checking:
string mainString = "Hello, World!";
string subString = "World";
size_t position = [Link](subString);
if (position != string::npos) { // not equal to no-position
cout << "Substring found at position " << position << endl;
} else {
cout << "Substring not found." << endl;
}
29
Substring Checking:
string mainString = "Hello, World!";
string subString = "World";
for (size_t i = 0; i <= [Link]() - [Link](); i++) {
if ([Link](i, [Link]()) == subString) {
cout << "Substring found at position " << i << endl;
break;
}
30
A Subsequence is a sequence that can be derived from another sequence by deleting some or no elements without
changing the order of the remaining elements. In other words, a subsequence is obtained by selecting any subset of
characters from the original string, while preserving their relative order.
For example, consider the string "abcd". The subsequences of this string are: "", "a", "b", "c", "d", "ab", "ac", "ad", "bc",
"bd", "cd", "abc", "abd", "acd", "bcd", "abcd".
31
Implementation:
void printAllSubsequence(string input_str, string output_str){
if (input_str.empty()) {
cout << output_str << endl;
return;
}
printAllSubsequence(input_str.substr(1), output_str + input_str[0]);
printAllSubsequence(input_str.substr(1), output_str);
}
int main(){
string output_str = "";
string input_str = "abcd";
printAllSubsequence(input_str, output_str);
return 0;
}
Time Complexity: O(2^n)
Space Complexity: O(n)
32
Mathematical Operations Using Strings
Char to Int:
Converting Integers to String:
int number = 12345;
string numberStr = to_string(number);
33
Mathematical Operations Using Strings
BigInt Addition
string addBigInt(string a, string b) {
int carry = 0; Link: [Link]
string result = "";
int i = [Link]() - 1, j = [Link]() - 1;
while (i >= 0 || j >= 0 || carry) {
int sum = carry;
if (i >= 0) sum += (a[i--] - '0');
if (j >= 0) sum += (b[j--] - '0');
result = char(sum % 10 + '0') + result;
carry = sum / 10;
}
return result;
}
34
Mathematical Operations Using Strings
BigInt Subtraction
string subtractBigInt(string a, string b) {
string result = "";
int borrow = 0;
int i = [Link]() - 1, j = [Link]() - 1;
while (i >= 0 || j >= 0) {
int diff = borrow + (i >= 0 ? a[i--] - '0' : 0) - (j >= 0 ? b[j--] - '0' : 0);
if (diff < 0) {
diff += 10;
borrow = -1;
} else {
borrow = 0;
}
result = char(diff + '0') + result;
}
return result;
}
35
Mathematical Operations Using Strings
[Link]
Self Study – multiplication and division from the given code
36
String
Input:
2
Ab cd
Ef gh
Output:
______
Ab cd
37
String
Input:
2
Ab cd
Ef gh
Output:
Ab cd
Ef gh
38
Problems:
stringstream:
1. [Link]
Substring:
1. [Link]
2. [Link]
3. [Link]
Subsequence:
1. [Link]
2. [Link]
3. [Link]
String Functions
1. [Link]
2. [Link]
3. [Link]
Palindrome Check:
1. [Link]
39