## Big O(n^2) Ascending Sort

1 like • Nov 18, 2022 • 6 views
C++

## More C++ Posts

#### Daily: Find missing array value

0 likes • Aug 5, 2023 • 5 views
C++
```/*Good morning! Here's your coding interview problem for today.
This problem was asked by Stripe.
Given an array of integers, find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well.
For example, the input [3, 4, -1, 1] should give 2. The input [1, 2, 0] should give 3.
You can modify the input array in-place.*/#include <iostream>using namespace std;
int calcMissing(int* input, int size){	int sum = 0;	int n = 1; //add one to account for missing value	for(int i = 0; i < size; i++)	{	if(input[i] > 0)	{	sum += input[i];	n++;	}	}
//If no numbers higher than 0, answer is 1	if(sum == 0)	return 1;
return (n*(n+1)/2) - sum; //Formula is expectedSum - actualSum	/* expectedSum = n*(n+1)/2, the formula for sum(1, n) */}
int main(){
cout << calcMissing(new int[4]{3, 4, -1, 1}, 4) << endl;	cout << calcMissing(new int[3]{1, 2, 0}, 3) << endl;
//No positive numbers	cout << calcMissing(new int[1]{0}, 1) << endl;}```

#### Wing Project 1

0 likes • Oct 31, 2021 • 1 view
C++
```//Get data file at https://codecatch.net/post.php?postID=91e87d73//Iteration 1 of Wing Project. Solution breaks down around n=35
#include <iostream>#include <fstream>#include <string>#include <vector>#include <map>using namespace std;
int getSum(map<int, int> list);void readData(map<int, float>* data);void lowestPrice();void findSums(int n, vector<map<int, int>>* sumsList, map<int, float>* data);//void findSum(map<int, int> currList, int x, int n, vector<map<int, int>>* sumsList);void findSum(map<int, int> currList, int x, int n, vector<map<int, int>>* sumsList, map<int, float>* data);float getPrice(map<int, int> set, map<int, float>* data);
template <typename S>ostream& operator<<(ostream& os, const vector<S>& vector){	// Printing all the elements using <<	for (auto element : vector) {	os << element << " ";	}	return os;}
bool operator==(map<int, int> m1, map<int, int> m2){	if(m1.size() != m2.size())	return false;
bool ret = true;
for(auto it = m1.begin(); it !=m1.end() && ret; it++)	{	if(ret && m1.count(it->first) != m2.count(it->first))	ret = false;
if(ret && m1.count(it->first) == 1)	{	if(m1.at(it->first) != m2.at(it->first))	ret = false;	}	}
return ret;}

int main(){	map<int, float> data;	readData(&data);
vector<map<int, int>> *sumsList;	sumsList = new vector<map<int, int>>;	findSums(40, sumsList, &data);
for(auto el : *sumsList)	{	for(auto it = el.begin(); it != el.end(); it++)	{	cout << it->first << "->" << it->second << " ";	}	cout << getPrice(el, &data) << endl;	}
return 0;}
/* Returns the price of wings given a set of numbers of wings to buy.	* Returns -1 if the set contains a number that is not possible to buy.	*/float getPrice(map<int, int> set, map<int, float>* data){	float price = 0;	for(auto it = set.begin(); it != set.end(); it++)	{	//If data doesn't contain an element of set, return -1	if(data->count(it->first) == 0)	return -1;		price += data->at(it->first) * it->second; //pricePerPacket * qtyOfPackets	}
return price;}
/* Adds the elements of list.	* Suppose mapping is <num, qty>.	* Returns sum(num*qty)	*/int getSum(map<int, int> list){	int sum = 0;	for(auto it = list.begin(); it != list.end(); it++)	sum += it->first * it->second;	return sum;}
void findSums(int n, vector<map<int, int>>* sumsList, map<int, float>* data){	map<int, int> currList;
//Recur when currSum < n	auto it = data->begin();	while(it->first <= n && it != data->end())	{	findSum(currList, it->first, n, sumsList, data);	it++;	}}
void findSum(map<int, int> currList, int x, int n, vector<map<int, int>>* sumsList, map<int, float>* data){	//Append x to currList	if(currList.count(x) == 0)	currList.emplace(x, 1);	else	{	int val = 1+ currList.at(x);	currList.erase(x);	currList.emplace(x, val);	}
//Determine current sum, check for return cases	int currSum = getSum(currList);
if(currSum > n)	return;	else if(currSum == n)	{
//Check to make sure no duplicates	for(auto list : *sumsList)	{	if(list == currList)	return;	}
sumsList->push_back(currList);	return;	}
//Recur when currSum < n	auto it = data->begin();	while(it->first <= n-x && it != data->end())	{	findSum(currList, it->first, n, sumsList, data);	it++;	}}
void readData(map<int, float>* data){	ifstream file ("./data", ifstream::in);
if(file.is_open())	{	int i = 0;	while(!file.eof())	{	float wings, price;	string skipnl;	file >> wings;	file >> price;
data->emplace(wings, price);
getline(file, skipnl);	i++;	}	}}```

#### C++ Range Slicer

0 likes • Oct 31, 2023 • 3 views
C++
```//Leif Messinger//Compile with C++ 20#include <iostream>#include <ranges>#include <vector>#include <functional>#include <cctype> //toupper#include <cxxabi.h>
template <typename T>void printType(){    std::cout << abi::__cxa_demangle(typeid(T).name(), NULL, NULL, NULL) << std::endl;}
template <typename T>class Slicer{    public:        T begin_;        T end_;        T trueEnd;        Slicer(T begin, T end): begin_(begin), end_(begin), trueEnd(end){}        template<typename U>        Slicer(U&& vec) : begin_(vec.begin()), end_(vec.begin()), trueEnd(vec.end()){}        Slicer& finish(){            begin_ = end_;            end_ = trueEnd;            return (*this);        }        Slicer& to(long int index){            begin_ = end_;            if(index > 0){                end_ = (begin_ + index);            }else{                index *= -1;                end_ = (trueEnd - index);            }            return (*this);        }        Slicer& operator[](long int index){            return to(index);        }        T begin(){            return this->begin_;        }        T end(){            return this->end_;        }        Slicer& operator()(std::function<void(decltype(*begin_))> func) {            for(decltype(*begin_) thing : (*this)){                func(thing);            }            return (*this);        }};static_assert(std::ranges::range< Slicer<std::vector<int>::const_iterator> >);
int main(){    std::string vec = "abcdefghijklmnopqrstuvwxyz";    Slicer<std::string::const_iterator> bruh(vec);        //printType<decltype(bruh)>();
bruh.to(3)([](char yeet){        std::cout << yeet;    })    .to(-1)([](char yeet){        std::cout << char(std::toupper(yeet));    }).finish()([](char yeet){        std::cout << yeet << yeet << yeet << yeet << yeet;    });        std::cout << std::endl << std::endl;        int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};    Slicer<int*> arrSlicer(arr, arr + (sizeof(arr)/sizeof(int)));        std::cout << "[";    arrSlicer.to(-1)([](int yeet){        std::cout << yeet << ", ";    }).finish()([](int yeet){        std::cout << yeet << "]" << std::endl;    });
return 0;}```

#### CSCE 1040 Lab 9

0 likes • Nov 18, 2022 • 2 views
C++
```#include <iostream>#include "PlaylistNode.h"using namespace std;void PrintMenu(string title);
int main() {   string plTitle;   cout << "Enter playlist's title:" << endl;   getline(cin, plTitle);   PrintMenu(plTitle);   return 0;}
void PrintMenu(string title) {   Playlist list;   string id;   string sname;   string aname;   int length;   int oldPos;   int newPos;   char choice;      while(true) {      cout << endl << title << " PLAYLIST MENU" << endl;      cout << "a - Add song" << endl;      cout << "d - Remove song" << endl;      cout << "c - Change position of song" << endl;      cout << "s - Output songs by specific artist" << endl;      cout << "t - Output total time of playlist (in seconds)" << endl;      cout << "o - Output full playlist" << endl;      cout << "q - Quit" << endl << endl;            cout << "Choose an option:" << endl;      cin >> choice;      cin.ignore();            if (choice == 'q') {         exit(1);      }      else if (choice == 'a') {         cout << "\nADD SONG" << endl;         cout << "Enter song's unique ID: ";         cin >> id;         cin.ignore();         cout << "Enter song's name: ";         getline(cin,sname);         cout << "Enter artist's name: ";         getline(cin,aname);         cout << "Enter song's length (in seconds): ";         cin >> length;         list.AddSong(id, sname, aname, length);      }      else if (choice == 'd') {         cout << "\nREMOVE SONG" << endl;         cout << "Enter song's unique ID: ";         cin >> id;         list.RemoveSong(id);      }      else if (choice == 'c') {         cout << "\nCHANGE POSITION OF SONG" << endl;         cout << "Enter song's current position: ";         cin >> oldPos;         cout << "Enter new position for song: ";         cin >> newPos;         list.ChangePosition(oldPos, newPos);      }      else if (choice == 's') {         cout << "\nOUTPUT SONGS BY SPECIFIC ARTIST" << endl;         cout << "Enter artist's name: ";         getline(cin, aname);         list.SongsByArtist(aname);      }      else if (choice == 't') {         cout << "\nOUTPUT TOTAL TIME OF PLAYLIST (IN SECONDS)" << endl;         cout << "Total time: " << list.TotalTime() << " seconds" << endl;      }      else if (choice == 'o') {         cout << endl << title << " - OUTPUT FULL PLAYLIST" << endl;         list.PrintList();      }      else {         cout << "Invalid menu choice! Please try again." << endl;      }   }}```

#### wordScore.cpp

0 likes • Apr 16, 2023 • 0 views
C++
```#include <iostream>#include <string>	//Should already be in iostream#include <cstdlib>
//A word score adds up the character values. a-z gets mapped to 1-26 for the values of the characters.
//wordScore [wordValue]//Pipe in the input into stdin, or type the words yourself.
//Lowercase words onlyint characterValue(const char b){	return ((b >= 'a') && (b <= 'z'))? ((b - 'a') + 1) : 0;}
int main(int argc, char** argv){    //The first argument specifies if you are trying to look for a certain word score	int wordValue = (argc > 1)? std::atoi(argv[1]) : 0;
std::string line;	while(std::getline(std::cin, line)){		int sum = 0;		for(const char c : line){			sum += characterValue(c);		}		if(wordValue){	//If wordValue is 0 or the sum is the correct value			if(wordValue == sum){				std::cout << line << std::endl;			}		} else {			std::cout << sum << "\t" << line << std::endl;		}	}	return 0;}```

#### BFS/DFS/TopSort

0 likes • Apr 30, 2021 • 3 views
C++
```#include <bits/stdc++.h>#define MAXSIZE 50000#define INF 100000
using namespace std;
bool visited[MAXSIZE]; //Checks if a node is visited or not in BFS and DFSbool isConnected = true; //Checks if the input graph is connected or not
int dist[MAXSIZE], discover[MAXSIZE], finish[MAXSIZE]; //Distance for BFS, in time and out time for DFSint t = 1; //Time used for DFSint u, v, i, j, k, N = 0;
stack<int> st; //Stack for TopSort
multiset<pair<int, int>> s; //collection of pairs to sort by distancepair<int, int> current; //pointer variable to a position in the multiset
void BFS(){	queue<int> q; //queue for BFS	q.push(1); //pushing the source	dist[1] = 0; //assign the distance of source as 0	visited[1] = 1; //marking as visited		while(!q.empty())	{	u = q.front();	q.pop();
if(!visited[v]) //if not visited, update the distance and push onto queue	{	visited[v] = 1;	dist[v] = dist[u]+1;	q.push(v);	}
}
}		for(i = 1; i <= N; i++)	{	s.insert(make_pair(dist[i], i)); //for sorted distance	}		cout << "BFS results:" << endl;		//prints BFS results and checks if the graph is connected	while(!s.empty())	{	current = *s.begin(); 	s.erase(s.begin());
i = current.second; 	j = current.first;
if(j == INF) //if any infinite value, graph is not connected	{	cout << i << " INF" << endl;	isConnected = false;	}	else	{	cout << i << " " << j << endl;	}
}
//marks blocks of memory as visited	memset(visited, 0, sizeof visited);}

void dfsSearch(int s){	visited[s] = 1; //marking it visited	discover[s] = t++; //assigning and incrementing time
int i, v;
if(!visited[v]) //if vertex is not visited then visit, else continue	{	dfsSearch(v);	}
}
st.push(s); //pushed onto stack for TopSort if it was called	finish[s] = t++; //out time}
void DFS(){
for(i = 1; i <= N; i++)	{	if(visited[i]) //if visited continue, else visit it with DFS	{	continue;	}
dfsSearch(i); //embedded function to actually perform DFS	}
for(i=1;i<=N;i++)	{	s.insert(make_pair(discover[i], i)); //minheap for sorted discovery time	}		cout << "DFS results:" << endl;
while(!s.empty()) //Prints DFS results as long as the multiset is not empty	{	current = *s.begin(); //duplicates the pointer to first object in the multiset	s.erase(s.begin()); //erases the first object in multiset
i = current.second;	cout << i << " " << discover[i] << " " << finish[i] << endl; //prints discover times and finish times	}
}
void TopSort(){	//call DFS so we can have a sorted stack to print	for(i=1;i<=N;i++)	{	if(visited[i])	{	continue;	}
dfsSearch(i);	}
cout<<"Topological Sort results:"<<endl;
//print sorted results from DFS	while(!st.empty())	{	i = st.top(); 	st.pop();
cout << i << endl;	}
//declare blocks of memory as visited	memset(visited, 0, sizeof visited);
}

int main(){	string str, num, input;	int selection, connectedChoice = 0;

//get to input any file, more freedom than declaring file in command line	cout << "Enter the exact name of your input file [case sensitive]: ";	cin >> input;		ifstream inputFile(input); //Read the input file
//checks if the ifstream cannot open	if(inputFile.fail())	{	cout << endl << "No input files matching that name. Terminating..." << endl;	return 0;	}
//Read until the end of file	while(!inputFile.eof())	{	getline(inputFile, str); //read the current line
if(str == "")	{	continue;	}
if(!isdigit(str[0])) //checks to see if the first item in a line is a digit or not	{	cout << "Invalid file format. You have a line beginning with a non-digit. Terminating..." << endl;	return 0;	}
stringstream ss;	ss << str; //convert the line to stream of strings		ss >> num; //read the line num	stringstream(num) >> u;		while(!ss.eof())	{	ss>>num;	if(stringstream(num) >> v)	{	adj[u].push_back(v); //read the adjacent vertices	}	}
N++; //calculate the number of vertices	sort(adj[u].begin(), adj[u].end()); //sort the adjacency list in case it is not sorted	}		//creates arbitrary values for distance, will check later if INF remain	for(i = 1; i <= N; i++)	{	dist[i] = INF;	}
cout << endl << "Valid Input file loaded!" << endl;
while(selection != 4)	{	cout << "************************************************" << endl;	cout << "What type of analysis would you like to perform?" << endl;	cout << "1: Breadth-First Search" << endl;	cout << "2: Depth-First Search" << endl;	cout << "3: Topological Sort" << endl;	cout << "4: Quit" << endl;	cout << "************************************************" << endl;		//read user input and execute selection	cin >> selection;
switch(selection)	{	case 1:	cout << endl;	BFS();	cout << endl;	cout << "Would you like to know if the graph is connected?" << endl;	cout << "1: Yes" << endl;	cout << "Any other key: No" << endl;	cin >> connectedChoice;
switch(connectedChoice)	{	case 1:	if(!isConnected)	{	cout << "The graph is not connected." << endl << endl;	}	else	{	cout << "The graph is connected!" << endl << endl;	}	break;	default:	break;	}	break;	case 2:	cout << endl;	DFS();	cout << endl;	break;	case 3:	cout << endl;	TopSort();	cout << endl;	break;	case 4:	return 0;	default:	cout << endl << "Invalid selection." << endl; //loops the selection prompt until a valid selection is input.	}
}	}```