Skip to content

Instantly share code, notes, and snippets.

@vo
Created August 17, 2016 19:42
Show Gist options
  • Save vo/ce02567f2b675587030bbf8a1c61cb38 to your computer and use it in GitHub Desktop.
Save vo/ce02567f2b675587030bbf8a1c61cb38 to your computer and use it in GitHub Desktop.
Programming Practice: Finding supermajority character in a string
#include <iostream>
char findSuperMajority(const std::string &str)
{
const size_t len(str.length());
int count(0);
char val(str[0]);
for (char c : str) {
if (count == 0) {
val = c;
count = 1;
} else if (val == c) {
count++;
} else {
count--;
}
}
count = 0;
for (char c : str) {
if (c == val) {
count++;
}
}
if (count <= len / 2) {
return 0;
}
return val;
}
int main()
{
std::string inputString;
while (std::cin >> inputString) {
char superMajority = findSuperMajority(inputString);
if (superMajority != 0) {
std::cout << "Super Majority: " << superMajority << std::endl;
} else {
std::cout << "Super Majority NOT FOUND" << std::endl;
}
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment