forked from gouthampradhan/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathFindTheClosestPalindrome.java
More file actions
121 lines (113 loc) · 5.19 KB
/
FindTheClosestPalindrome.java
File metadata and controls
121 lines (113 loc) · 5.19 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
package string;
/**
* Created by gouthamvidyapradhan on 21/04/2018.
* Given an integer n, find the closest integer (not including itself), which is a palindrome.
The 'closest' is defined as absolute difference minimized between two integers.
Example 1:
Input: "123"
Output: "121"
Note:
The input n is a positive integer represented by string, whose length will not exceed 18.
If there is a tie, return the smaller one as answer.
Solution O(N): General idea is to consider the first half of the string and make a new string by reversing the first
half of string. Concatenate the first_half and the new_string and return this as an answer. There are also
a lot of edge cases to be considered using this approach.
*/
public class FindTheClosestPalindrome {
public static void main(String[] args) throws Exception {
System.out.println(new FindTheClosestPalindrome().nearestPalindromic("1837722381"));
}
public String nearestPalindromic(String n) {
if(n.length() == 1) return String.valueOf(Integer.parseInt(n) - 1);
String p1, p2;
String palindrome;
if(isPaliandrome(n)){
String newFirstHalf;
if(n.length() % 2 == 0){
String firstHalf = n.substring(0, n.length() / 2);
newFirstHalf = String.valueOf(Long.parseLong(firstHalf) - 1);
p1 = newFirstHalf + new StringBuilder(newFirstHalf).reverse();
newFirstHalf = String.valueOf(Long.parseLong(firstHalf) + 1);
p2 = newFirstHalf + new StringBuilder(newFirstHalf).reverse();
} else{
String firstHalf = n.substring(0, n.length() / 2);
char middle = n.charAt(n.length() / 2);
if(middle == '0'){
p1 = firstHalf + "1" + new StringBuilder(firstHalf).reverse();
} else{
p1 = firstHalf + (Integer.parseInt(String.valueOf(middle)) - 1) + new StringBuilder
(firstHalf).reverse();
}
newFirstHalf = String.valueOf(Long.parseLong(firstHalf) + 1);
p2 = newFirstHalf + "0" + new StringBuilder(newFirstHalf).reverse();
}
}else{
String firstHalf = n.substring(0, n.length() / 2);
if(n.length() % 2 == 0){
p1 = firstHalf + new StringBuilder(firstHalf).reverse();
String temp = String.valueOf(Long.parseLong(firstHalf) + 1);
p2 = temp + new StringBuilder(temp).reverse();
temp = String.valueOf(Long.parseLong(firstHalf) - 1);
String p3 = temp + new StringBuilder(temp).reverse();
p1 = Math.abs(Long.parseLong(p3) - Long.parseLong(n)) <= Math.abs(Long.parseLong(p1) - Long.parseLong
(n)) ? p3 : p1;
} else {
char middle = n.charAt(n.length() / 2);
p1 = firstHalf + middle + new StringBuilder(firstHalf).reverse();
String temp = String.valueOf(Long.parseLong(firstHalf) + 1);
p2 = temp + "0" + new StringBuilder(temp).reverse();
String p3 = firstHalf + (Integer.parseInt(String.valueOf(middle)) + 1) + new StringBuilder(firstHalf)
.reverse();
String p4 = null;
if(middle != '0'){
p4 = firstHalf + (Integer.parseInt(String.valueOf(middle)) - 1) + new StringBuilder
(firstHalf).reverse();
}
p1 = Math.abs(Long.parseLong(p1) - Long.parseLong(n)) <= Math.abs(Long.parseLong(p3) - Long.parseLong
(n)) ? p1 : p3;
if(p4 != null){
p1 = Math.abs(Long.parseLong(p4) - Long.parseLong(n)) <= Math.abs(Long.parseLong(p1) - Long
.parseLong(n)) ? p4 : p1;
}
}
}
long l1 = Math.abs(Long.parseLong(n) - Long.parseLong(p1));
long l2 = Math.abs(Long.parseLong(n) - Long.parseLong(p2));
if(l1 <= l2){
palindrome = p1;
} else palindrome = p2;
long m1 = Math.abs(Long.parseLong(getLow(n)) - Long.parseLong(n));
long m2 = Math.abs(Long.parseLong(palindrome) - Long.parseLong(n));
long m3 = Math.abs(Long.parseLong(getHigh(n)) - Long.parseLong(n));
long min = Math.min(Math.min(m1, m2), m3);
if(min == m1) return getLow(n);
else if(min == m2) return palindrome;
else return getHigh(n);
}
private String getLow(String s){
int n = s.length() - 1;
StringBuilder sb = new StringBuilder();
for(int i = 0; i < n; i ++){
sb.append("9");
}
return sb.toString();
}
private String getHigh(String s){
int n = s.length() - 1;
StringBuilder sb = new StringBuilder();
sb.append("1");
for(int i = 0; i < n; i ++){
sb.append("0");
}
sb.append("1");
return sb.toString();
}
private boolean isPaliandrome(String s){
for(int i = 0, j = s.length() - 1; i < j; i++, j--){
if(s.charAt(i) != s.charAt(j)){
return false;
}
}
return true;
}
}