java - Checking Palindromes using BigInteger -
i working on /r/dailyprogramming challenge calculate how many steps takes turn number palindromic number. e.g. 24 gets palindromic after 1 steps: 66 -> 24 + 42 = 66.
the program working however, 1 of inputs quite large, have chosen use biginteger solve overflow problem having regular integers.
originally using code similar found on leetcode check if value palindrome, worked input didn't cause overflow:
original code example used check if palindrome:
public int reverse(int x) { //flag marks if x negative boolean flag = false; if (x < 0) { x = 0 - x; flag = true; } int res = 0; int p = x; while (p > 0) { int mod = p % 10; p = p / 10; res = res * 10 + mod; } if (flag) { res = 0 - res; } return res; }
i have since updated code account use of biginteger's. updated code loops indefinitely, palindrome never detected, continues reverse , add - have stepped through program few times , unable determine have incorrectly transposed original code have written.
making_numbers_palindromic:
public class making_numbers_palindromic { private biginteger originalnumber; private int count = 0; public void run(biginteger number) { assert (checkpositive(number)); originalnumber = number; boolean flag = false; while (!flag) { if (checkpalindrome(number)) { system.out.printf("%d gets palindromic after" + "%d steps: %d", originalnumber, count, number); system.exit(1); } number = addreverse(number); count++; } } /** * @param number * @return biginteger#signum returns 1 if value positive */ public boolean checkpositive(biginteger number) { if (number.compareto(biginteger.zero) == 1) { return true; } return false; } public boolean checkpalindrome(biginteger number) { if (number.compareto(biginteger.zero) < 0) return false; biginteger div = new biginteger("1"); while ((number.divide(div)).compareto(biginteger.ten) >= 0) { div = div.multiply(biginteger.ten); } while (!number.equals(new biginteger("0"))) { biginteger len = number.divide(div); biginteger revs = number.mod(biginteger.ten); if (!len.equals(revs)) return false; number = (number.mod(div)).divide(biginteger.ten); div = div.divide(biginteger.ten); } return true; } public biginteger addreverse(biginteger number) { return number.add(reverse(number)); } public biginteger reverse(biginteger number) { boolean flag = false; biginteger reverse = new biginteger("0"); biginteger numcopy = number; if (number.compareto(biginteger.zero) == -1) { flag = true; } while (numcopy.compareto(biginteger.zero) > 0) { biginteger mod = numcopy.mod(biginteger.ten); numcopy = numcopy.divide(biginteger.ten); reverse = (reverse.multiply(biginteger.ten)).add(mod); } if (flag) { reverse = biginteger.zero.subtract(reverse); } return reverse; } }
this first time using biginteger , have taken @ javadocs - cannot see apparent may wrong usage of biginteger#compare or biginteger#equals
the main method:
public class bootstrap { public static void main(string[] args) { making_numbers_palindromic mnp = new making_numbers_palindromic(); if (args.length > 0) { mnp.run(biginteger.valueof(integer.parseint(args[0]))); } else { system.out.printf("usage: palindromic number"); } } }
i plan make making_numbers_palindromic private constructor can use utility class, have not got around yet.
thank-you
not sure if that's error, in checkpalindrome
div = div.divide(biginteger.ten);
should be
div = div.divide(biginteger.valueof(100));
since after compare first , last digits of number, discard them, div
of next iterations should 100 times smaller current div
.
that said, after fix bugs, doing double work should doing, since if reverse number, can use reversed number determine if original palindrome (by comparing original reversed number).
Comments
Post a Comment