The idea of a strobogrammatic number in the fields of mathematics and computer science is quite intriguing as it refers to a number that maintains its original form even when rotated 180 degrees (flipped upside down). These numbers exhibit symmetry in their arrangement and are commonly applied in scenarios related to palindromes, rotations, and recognizing patterns. Instances of strobogrammatic numbers include single-digit figures like 0, 1, and 8, along with multi-digit sequences such as 69, 96, and 818.
When a rotation of 180° is applied, specific digits retain their original appearance, namely 0, 1, and 8. Additionally, the digits 6 and 9 exhibit a unique symmetry, making them strobogrammatic as they transform into each other when rotated.
Conversely, digits like 2, 3, 4, 5, and 7 lack the necessary symmetry under rotation and are therefore ineligible for inclusion in strobogrammatic numbers.
Checking if a number is strobogrammatic is typically achieved through computational methods involving string manipulation. Employing a two-pointer technique allows for the comparison of digits at corresponding positions from both ends when the number is converted into a string. Each digit in the number must have a strobogrammatic counterpart for the number to be considered strobogrammatic.
In practice, strobogrammatic numbers are used in many different fields, such as in cryptography, digital clock displays, and aesthetic designs in visual arts. On the other hand, in programming challenges, they appear on tasks to process strings, rotational symmetry, and pattern matching. As an example, in order to find strobogrammatic numbers in C++ , an unordered map is used to store pairs of valid digits, and the program checks if the string turns on the map correctly to its rotated equivalent.
Approach-1: Two-Pointer Approach
Strobogrammaticity is verified by examining digits at corresponding mirrored positions through the Two-Pointer Technique. This method requires positioning two pointers: one at the beginning (left) and the other at the end (right) of the numeric string representation.
The fundamental requirement is that the pointer in the leftmost position must correspond to a valid strobogrammatic pair with the digit on the right side. Valid pairs include 0 ↔ 0, 1 ↔ 1, 8 ↔ 8, 6 ↔ 9, 9 ↔ 6, and so on. For instance, if the digit on the left is 6, then the digit on the right must be 9 to form a strobogrammatic number.
However, the process continues by advancing both pointers inward (left++ and right--) until they converge or overlap. The assessment of whether the number is strobogrammatic involves verifying the absence of any discrepancies (such as an incorrect digit or mismatched pair). A number is considered strobogrammatic when all pairs correspond correctly.
Example:
Let's consider an instance to demonstrate the concept of Strobogrammatic Numbers in C++ by employing the two-pointer technique.
#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>
#include <sstream>
#include <cctype>
#include <iomanip>
// Function to check if a number is strobogrammatic
bool isStrobogrammatic(const std::string& num) {
std::unordered_map<char, char> strobogrammaticPairs = {
{'0', '0'}, {'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'}
};
int left = 0, right = num.size() - 1;
while (left <= right) {
// Check if the current digit has a valid pair
if (strobogrammaticPairs.find(num[left]) == strobogrammaticPairs.end() ||
strobogrammaticPairs[num[left]] != num[right]) {
return false;
}
left++;
right--;
}
return true;
}
// Function to validate user input
bool validateInput(const std::string& input) {
for (char c : input) {
if (!isdigit(c)) return false;
}
return !input.empty();
}
// Function to explain the checking process
std::string explainProcess(const std::string& num) {
std::unordered_map<char, char> strobogrammaticPairs = {
{'0', '0'}, {'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'}
};
int left = 0, right = num.size() - 1;
std::stringstream explanation;
explanation << "Checking process for number: " << num << "\n";
while (left <= right) {
char leftChar = num[left];
char rightChar = num[right];
explanation << "Comparing '" << leftChar << "' (left) with '" << rightChar
<< "' (right)... ";
if (strobogrammaticPairs.find(leftChar) == strobogrammaticPairs.end()) {
explanation << "Invalid digit '" << leftChar << "' (not strobogrammatic).\n";
return explanation.str();
}
if (strobogrammaticPairs[leftChar] != rightChar) {
explanation << "Mismatch: '" << leftChar << "' maps to '"
<< strobogrammaticPairs[leftChar] << "', but '" << rightChar
<< "' found.\n";
return explanation.str();
}
explanation << "Valid match! '" << leftChar << "' ↔ '" << rightChar << "'\n";
left++;
right--;
}
explanation << "All pairs are valid! The number is strobogrammatic.\n";
return explanation.str();
}
// Function to generate some sample numbers for testing
std::vector<std::string> generateSampleNumbers() {
return {"69", "88", "818", "123", "609", "986", "1", "11", "0", "121","456","737"};
}
// Function to display results in a custom output format
void displayResults(const std::vector<std::string>& numbers) {
for (const auto& num : numbers) {
std::cout << "Number: " << num << "\n";
std::cout << "Result: "
<< (isStrobogrammatic(num) ? "Strobogrammatic" : "Not Strobogrammatic")
<< "\n";
std::cout << explainProcess(num) << "\n";
}
}
// Main function
int main() {
std::cout << " Strobogrammatic Number Checker \n";
// Step 1: Display some sample results
std::vector<std::string> sampleNumbers = generateSampleNumbers();
std::cout << "\nSample Numbers and Results:\n";
displayResults(sampleNumbers);
// Step 2: Allow user to input their own numbers
std::string userInput;
while (true) {
std::cout << "\nEnter a number to check (or type 'exit' to quit): ";
std::cin >> userInput;
if (userInput == "exit") {
std::cout << "Exiting the program. Goodbye!\n";
break;
}
if (!validateInput(userInput)) {
std::cout << "Invalid input! Please enter a non-negative integer.\n";
continue;
}
std::cout << "Number: " << userInput << "\n";
std::cout << "Result: "
<< (isStrobogrammatic(userInput) ? "Strobogrammatic" : "Not Strobogrammatic")
<< "\n";
std::cout << explainProcess(userInput) << "\n";
}
return 0;
}
Output:
Strobogrammatic Number Checker
Sample Numbers and Results:
Number: 69
Result: Strobogrammatic
Checking process for number: 69
Comparing '6' (left) with '9' (right)... Valid match! '6' ↔ '9'
All pairs are valid! The number is strobogrammatic.
Number: 88
Result: Strobogrammatic
Checking process for number: 88
Comparing '8' (left) with '8' (right)... Valid match! '8' ↔ '8'
All pairs are valid! The number is strobogrammatic.
Number: 818
Result: Strobogrammatic
Checking process for number: 818
Comparing '8' (left) with '8' (right)... Valid match! '8' ↔ '8'
Comparing '1' (left) with '1' (right)... Valid match! '1' ↔ '1'
All pairs are valid! The number is strobogrammatic.
Number: 123
Result: Not Strobogrammatic
Checking process for number: 123
Comparing '1' (left) with '3' (right)... Mismatch: '1' maps to '1', but '3' found.
Number: 609
Result: Strobogrammatic
Checking process for number: 609
Comparing '6' (left) with '9' (right)... Valid match! '6' ↔ '9'
Comparing '0' (left) with '0' (right)... Valid match! '0' ↔ '0'
All pairs are valid! The number is strobogrammatic.
Number: 986
Result: Strobogrammatic
Checking process for number: 986
Comparing '9' (left) with '6' (right)... Valid match! '9' ↔ '6'
Comparing '8' (left) with '8' (right)... Valid match! '8' ↔ '8'
All pairs are valid! The number is strobogrammatic.
Number: 1
Result: Strobogrammatic
Checking process for number: 1
Comparing '1' (left) with '1' (right)... Valid match! '1' ↔ '1'
All pairs are valid! The number is strobogrammatic.
Number: 11
Result: Strobogrammatic
Checking process for number: 11
Comparing '1' (left) with '1' (right)... Valid match! '1' ↔ '1'
All pairs are valid! The number is strobogrammatic.
Number: 0
Result: Strobogrammatic
Checking process for number: 0
Comparing '0' (left) with '0' (right)... Valid match! '0' ↔ '0'
All pairs are valid! The number is strobogrammatic.
Number: 121
Result: Not Strobogrammatic
Checking process for number: 121
Comparing '1' (left) with '1' (right)... Valid match! '1' ↔ '1'
Comparing '2' (left) with '2' (right)... Invalid digit '2' (not strobogrammatic).
Number: 456
Result: Not Strobogrammatic
Checking process for number: 456
Comparing '4' (left) with '6' (right)... Invalid digit '4' (not strobogrammatic).
Number: 737
Result: Not Strobogrammatic
Checking process for number: 737
Comparing '7' (left) with '7' (right)... Invalid digit '7' (not strobogrammatic).
Enter a number to check (or type 'exit' to quit): exit
Exiting the program. Goodbye!
Explanation:
The
- isStrobogrammatic function serves as a Strobogrammatic Check function.
This function uses a two-pointer approach:
An unordered map is employed to associate valid strobogrammatic digit pairs (e.g., 0↔0, 1↔1, 8↔8, 6↔9, and 9↔6). The numerical loop is navigated by two pointers (left and right) from opposite ends, evaluating characters.
The function will produce a false result if the digit is not found in the map or if the mirrored counterpart of the digit does not match the digit itself.
- validateInput(input)
Validates that the input is a non-negative integer value:
We loop through each character in the string to determine if it is a numerical digit. This process verifies that the input is not devoid of any content.
- elucidateProcedure (Explanation Function)
This function provides a detailed walkthrough of the strobogrammatic check process:
It is similar to isStrobogrammatic, but it provides an additional message to each comparison (e.g. 'Valid match!' or "Mismatch"). It breaks down why the number isn’t strobogrammatic when there is a mismatch or invalid digit.
- generateSampleNumbers (Sample Generation)
It lists some example numbers to show how it works (e.g., 69, 818, 123).
- displayResults (Results Display)
It loops through a numerical list: describeProcess clarifies the rationale behind the strobogrammatic nature of each number, followed by indicating whether each number is strobogrammatic or not.
- User Interaction (Primary Function)
It generates outcomes for predetermined sampled figures. Guides the user to enter a number and validates the presence of input. The strobogrammatic verification is executed and displays a comprehensive description.
Output Format
For each numerical value, the software provides a detailed breakdown of the comparison process:
Results displayed corresponding pairs like '6' ↔ '9'. These linked matches or incorrect numbers are identified. The software has been crafted using a modular method, enhancing its resilience, ease of use, and thorough documentation.
Complexity Analysis:
Calculating the time complexity for the Strobogrammatic Check function (isStrobogrammatic):
This function operates on every digit once through the employment of two pointers (left and right) traversing the string. Consequently, the time complexity amounts to O(n), with n representing the input string's length (the quantity of digits in the number).
The search in the unordered map for every valid strobogrammatic pair involves iterating through each character in constant time complexity.
- Detailed Description Function (explainProcess):
It loops over the string once, similar to how we do in the isStrobogrammatic function, performing pairwise comparisons and explanations. As a result, even for a single number, the time complexity remains O(n).
- Validation Function (validateInput):
The checkdigit function iterates over each character within the string to validate if it is a numerical digit. Its time complexity is O(n) as it examines the complete string.
- Example Outcomes (displayResults):
The isStrobogrammatic and explainProcess functions are invoked for each individual sample number within the function that loops through all the sample numbers.
If we consider m sample values with an average length of n, the time complexity is O(m × n).
Space Utilization
- Checking Strobogrammaticity: This involves an unchanging map of a specific size (constant space, O(1)), with just two integer variables (left, right) used for referencing.
- Explanation Generation: This function constructs the explanation text through the stringstream method. It requires O(n) space to hold the explanations for n numbers. Overall, the space complexity for one number is O(n).
Approach-2: Hash-Based Validation
In the HashBased Validation technique, we substitute every numeral in the numeric sequence with its corresponding strobogrammatic counterpart stored in a hash table. The legitimate strobogrammatic counterparts (e.g., 0 ↔ 0, 1 ↔ 1, 6 ↔ 9, 9 ↔ 6, 8 ↔ 8) are stored in an unsorted dictionary. The process involves looping through the character sequence, replacing a digit with its counterpart, and constructing a modified string.
After the conversion process is finished, the converted string is then flipped. A number is considered strobogrammatic if the reversed string matches the initial input; if not, it does not meet the criteria. This method of transforming and comparing strings removes the necessity for employing a two-pointer approach and verifies the strobogrammatic property of the number.
Example:
Let's consider a scenario to demonstrate the Strobogrammatic Number concept in C++ by implementing a HashBased verification method.
#include <iostream>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <sstream>
#include <vector>
// Function to check if a number is strobogrammatic using hash-based transformation
bool isStrobogrammaticHash(const std::string& num) {
// Define valid strobogrammatic digit pairs
std::unordered_map<char, char> strobogrammaticPairs = {
{'0', '0'}, {'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'}
};
// Initialize an empty string to store the transformed number
std::string transformed;
// Transform each digit to its strobogrammatic pair
for (char c : num) {
// If a character is invalid (not in the map), return false immediately
if (strobogrammaticPairs.find(c) == strobogrammaticPairs.end()) {
return false;
}
transformed += strobogrammaticPairs[c]; // Add the transformed digit
}
// Reverse the transformed string
std::reverse(transformed.begin(), transformed.end());
// Compare the transformed string with the original number
return transformed == num;
}
// Function to validate if the input is a valid non-negative integer
bool validateInput(const std::string& input) {
// Ensure the input is non-empty and contains only digits
for (char c : input) {
if (!isdigit(c)) return false; // If non-digit is found, return false
}
return !input.empty();
}
// Function to display the result in a formatted manner
void displayResult(const std::string& num, bool isStrobogrammatic) {
std::cout << "Number: " << num << "\n";
std::cout << "Result: " << (isStrobogrammatic ? "Strobogrammatic" : "Not Strobogrammatic") << "\n";
}
// Function to explain the check process
std::string explainProcess(const std::string& num) {
std::unordered_map<char, char> strobogrammaticPairs = {
{'0', '0'}, {'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'}
};
std::stringstream explanation;
explanation << "Checking the number: " << num << "\n";
// Create a transformed string by replacing digits with their strobogrammatic pair
std::string transformed;
for (char c : num) {
if (strobogrammaticPairs.find(c) == strobogrammaticPairs.end()) {
explanation << "Invalid digit '" << c << "' found.\n";
return explanation.str(); // Return explanation if invalid digit is found
}
transformed += strobogrammaticPairs[c];
}
// Reverse the transformed string
std::reverse(transformed.begin(), transformed.end());
// Compare the transformed string with the original number
if (transformed == num) {
explanation << "The transformed string matches the original number. It's strobogrammatic.\n";
} else {
explanation << "The transformed string does not match the original number. It's not strobogrammatic.\n";
}
return explanation.str();
}
// Function to generate a few sample numbers for testing
std::vector<std::string> generateSampleNumbers() {
return {"69", "88", "818", "123", "609", "986", "1", "11", "0", "121"};
}
// Function to display results for a list of sample numbers
void displaySampleResults() {
std::vector<std::string> sampleNumbers = generateSampleNumbers();
for (const auto& num : sampleNumbers) {
bool result = isStrobogrammaticHash(num);
displayResult(num, result);
std::cout << explainProcess(num) << "\n";
}
}
// Main function
int main() {
std::cout << " Strobogrammatic Number Checker \n";
// Step 1: Show sample results
std::cout << "\nSample Results:\n";
displaySampleResults();
// Step 2: Allow user to input numbers and check if they are strobogrammatic
std::string userInput;
while (true) {
std::cout << "\nEnter a number to check (or type 'exit' to quit): ";
std::cin >> userInput;
if (userInput == "exit") {
std::cout << "Exiting the program. Goodbye!\n";
break;
}
// Validate input to ensure it's a valid non-negative integer
if (!validateInput(userInput)) {
std::cout << "Invalid input! Please enter a valid non-negative integer.\n";
continue;
}
// Check if the number is strobogrammatic and display the result
bool isStrobogrammatic = isStrobogrammaticHash(userInput);
displayResult(userInput, isStrobogrammatic);
// Display a detailed explanation
std::cout << explainProcess(userInput) << "\n";
}
return 0;
}
Output:
Strobogrammatic Number Checker
Sample Results:
Number: 69
Result: Strobogrammatic
Checking the number: 69
The transformed string matches the original number. It's strobogrammatic.
Number: 88
Result: Strobogrammatic
Checking the number: 88
The transformed string matches the original number. It's strobogrammatic.
Number: 818
Result: Strobogrammatic
Checking the number: 818
The transformed string matches the original number. It's strobogrammatic.
Number: 123
Result: Not Strobogrammatic
Checking the number: 123
Invalid digit '2' found.
Number: 609
Result: Strobogrammatic
Checking the number: 609
The transformed string matches the original number. It's strobogrammatic.
Number: 986
Result: Strobogrammatic
Checking the number: 986
The transformed string matches the original number. It's strobogrammatic.
Number: 1
Result: Strobogrammatic
Checking the number: 1
The transformed string matches the original number. It's strobogrammatic.
Number: 11
Result: Strobogrammatic
Checking the number: 11
The transformed string matches the original number. It's strobogrammatic.
Number: 0
Result: Strobogrammatic
Checking the number: 0
The transformed string matches the original number. It's strobogrammatic.
Number: 121
Result: Not Strobogrammatic
Checking the number: 121
Invalid digit '2' found.
Enter a number to check (or type 'exit' to quit): exit
Exiting the program. Goodbye!
Explanation:
- isStrobogrammaticHash Function: This function tells whether a given number (which is a string) is strobogrammatic. It utilizes an unordered_map (hash map) to define valid strobogrammatic digit pairs: '0' ↔ '0', '1' ↔ '1', '6' ↔ '9', '9' ↔ '6', and '8' ↔ '8'. It iterates through each character of the input string and changes them using the hash map. The function returns false if any character besides a key in the map is encountered because it is an invalid character. It reverses the string, compares it with converted digits, and then reverts it into a number. The number is strobogrammatic if they match.
- validateInput Function: This function just ensures that the input string contains only digits and is non-empty. Thereby, it rejects invalid inputs, which are alphabetic or special characters.
- displayResult Function: It is a function, which formats the result to indicate if the number itself is strobogrammatic or not.
- explainProcess Function: This function generates details of how it checks. It describes transform of each digit in comparison to a transformed string with the original.
- generateSampleNumbers Function: It produces a list of examples of the sample numbers used to display the program’s functionality.
- displaySampleResults Function: It goes through the sample numbers, checks if each number is strobogrammatic, and prints the results with an explanation.
- Main Function: It will display sample results and ask the user for input. It continuously validates and checks the entered number, which shows the result and explanations for that number. It allows the user to exit the program by typing "exit".
- Program Flow: The program shows results for some samples of numbers. After that, it goes in a loop where we input numbers to see if they are strobogrammatic. For an invalid input, the program asks for a valid input.
Complexity Analysis:
Time Complexity Analysis:
- isStrobogrammaticHash Function: Iterating Over the String: The num is a string of n-length characters, and the function processes each character of the string. On average, the lookup operation in the hash map (unordered map) is O(1). The second step named the string transformation step, adds the transformed digit to a new string (transformed). Each character this operation is performed for is O(1). Reversing the Transformed String: When all characters have been made into a string, the string is reversed. Reversing a string of length n takes O(n) time. Comparing the Transformed String: Finally, the transformed string is compared with the original string. It’s O(n) because it compares each character on both strings. As a result, the time complexity of isStrobogrammaticHash is dominated by string traversal, reversal, and comparison, all of which have time O(n). Total time complexity for this function: O(n).
- validateInput Function: This function loops through each character to see if they are a digit. As a loop is run once per character, the time complexity is O(n).
- displayResult and explainProcess: They are both string manipulation functions, where we have string combination, transformation, and string comparison. It means that these operations take time O(n).
- generateSampleNumbers and displaySampleResults: The sample generation and display operations take constant time because they use predefined set of sample numbers. Therefore, their time complexity is O(k), where k is a constant number of sample numbers.
Space Complexity Analysis:
- isStrobogrammaticHash: The unordered map strobogrammaticPairs stores 5 pairs of entries, and since it’s a fixed number of entries, the space complexity of the unordered map strobogrammaticPairs is O(1). A transformed string is created by storing the transformed version of the input string. We also note that this string is of length proportional to that of the input string, so we require O(n) space complexity.
- validateInput, displayResult, explainProcess: These functions require that a variable use up a small and fixed amount of space. For this reason, their space complexity is O(1).
- Sample Data: Sample numbers are stored in the vector of constant size (with k sample numbers). As a result, the generateSampleNumbers function has a space complexity of O(k).
