PROBLEM LINK:
Author: Ankush Khanna
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Given a large integer N and some modified rules, check whether N is a palindromic number according to the provided rules.
QUICK EXPLANATION:
Key to AC: Treat N as a string and just a linear string traversal and basic checking according to the rules will do the trick.
EXPLANATION:
The first and second sub tasks can be easily solved by using 32 bit and 64 bit integer representations of N respectively. But for the third sub task, we need to represent N as a string because it’s an extremely large number (1 \le N \le 10^{10^{5}}).
Let’s say S is the string representation of the integer N, and the number of digits in N is the length |S| of the string. So, mathematically, we can say that |S| = (\lfloor\log_{10}{N}\rfloor + 1).
First of all, the string S must not contain any 0 digit. For this part we just need to do a linear search on S to find if there is a 0. If we find a 0, we straightaway print false.
If there’s no 0 present, then we just need to check the first half and second half of the string with the rules provided (ignoring the middle character for odd length strings).
(All of the above mentioned things can be done in just a single string traversal)
The rules are very simple, every digit has a mirror image defined. The following are the digit pairs which are considered mirror images of each other:
1 \leftrightarrow 1
2 \leftrightarrow 7
3 \leftrightarrow 8
4 \leftrightarrow 5
6 \leftrightarrow 9
So we just need to check whether the digit at index i in S is a mirror image of the digit at index (|S| - i + 1) in S, that is, check whether S_{i} is a mirror image of S_{(|S| - i + 1)} (assuming 1-based indexing).
If we ever find any mismatch, then we print false, else true.
It’s as simple as that!
SOLUTION:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cout.setf(ios_base::boolalpha);
string image("0178549236");
int tt;
cin >> tt;
while (tt--) {
string s;
cin >> s;
if (s.find('0') != string::npos) {
cout << false << '\n';
continue;
}
bool mirror = true;
for (int i = 0, j = (int) s.size() - 1; mirror && i < j; i++, j--) {
mirror = s[i] == image[s[j] - '0'];
}
cout << mirror << '\n';
}
return 0;
}
COMPLEXITY:
Being a regular cakewalk problem, this problem is also solved in linear time, that is, the time complexity is O(|S|) or O(\log_{10}N) per test, which is linear in number of digits in N. So is the space complexity as well, because string representation of N will take O(\log_{10}{N}) space per test.
Feel free to share your approach. If you have any queries, they are always welcome.