Determining if an integer can be expressed as a palindromic sum

Question

I was asked this question in an interview:

An integer is special if it can be expressed as a sum that's a palindrome (the same backwards as forwards). For example, 22 and 121 are both special, because 22 equals 11+11 and 121 equals 29+92.

Given an array of integers, count how many of its elements are special.

but I couldn't think of any solution. How can this be done?

Answer 1

Question:

An integer is special if it can be expressed as a sum that's a palindrome (the same backwards as forwards). For example, 22 and 121 are both special, because 22 equals 11+11 and 121 equals 29+92.

Given an array of integers, count how many of its elements are special

My Approach:

public class PalindromicSum {

    public static void getSplNumber(int[] arrip) {
        //to iterate i/p array
        for (int i = 0; i < arrip.length; i++) {
            int tempSum = 0;
            //to iterate from 1 to number/2
            for (int j = 1; j <= arrip[i] / 2; j++) {
                //to get the reverse of the number
                int revNum = getRevNum(j);
                tempSum = revNum + j;
                if (tempSum == arrip[i]) {
                    System.out.println(arrip[i]);
                    break;
                } 
            }
        }
    }

    public static int getRevNum(int num) {
        int rev = 0;
        //to get reverse of a number
        while(num!=0) {
            int reminder = num%10;
            rev = rev*10 + reminder;
            num = num/10;
        }
        return rev;
    }

    public static void main(String[] args) {
        int[] arr = { 121, 11, 10, 3, 120, 110};
        getSplNumber(arr);

    }

}

Answer 2

Here is one of the brute-force approaches in JAVA and this can be optimised further,

import java.util.Scanner;

public class Solution {

public static void main(String[] args)
{
    Scanner in = new Scanner(System.in);
    
    String str = in.nextLine();
    String[] inp = str.split(",");
    
    System.out.println(isSpecial(inp,inp.length));
}

public static int isSpecial(String[] inp, int inpSize) 
{
    int arr[] = new int[inp.length];
    for(int i=0;i<inpSize;i++) 
    {
        arr[i] = Integer.parseInt(inp[i]);
    }
    
    int spclCount = 0;
    for(int i=0;i<arr.length;i++) 
    {
        for(int j=1;j<((arr[i]/2)+1);j++) 
        {
            if(j+getReverse(j) == arr[i]) 
            {
                spclCount++;
                break;
            }
        }
    }
    
    return spclCount;
}

public static int getReverse(int n) 
{
    int rem,rev=0;
    while(n != 0)
    {
        rem = n % 10;
        rev = (rev*10) + rem;
        n /= 10;
    }
    return rev;
}

}

Answer 3

Assuming we want two summands - this does not seem to be specified in the question but every answer has assumed it!

(Without this assumption, every number can be written as a reversible sum of 1s.)

Single digit summands:

n is even

Two digit summands:

10x + y + 10y + x

11x + 11y

11(x + y)

n is divisible by 11

Three digit summands:

100x + 10y + z + 100z + 10y + x

101x + 20y + 101z

101(x + z) + 20y

more complex but we can still
do better than a brute force
loop of 1 to n / 2

Etc... (we could probably write a function that generalises and searches over this algebra)

UPDATE

JavaScript code (interestingly, a result for 1111111110 seems to be found faster by the brute force 1 to n/2 loop! Maybe some other optimisations can be made):

function f(n){
  let start = new Date;
  let numDigits = 0;
  let t = Math.ceil(n / 2);
  while (t){
    numDigits++;
    t = ~~(t/10);
  }
  
  // Summands split between x and x+1 digits
  if (n / 2 + 0.5 == Math.pow(10, numDigits - 1))
    return false;

  let cs = [];
  let l = Math.pow(10, numDigits - 1);
  let r = 1;
  
  while (l >= r){
    cs.push(l + r);
    l /= 10;
    r *= 10;
  }
  
  let sxs = new Array(cs.length);
  const m = cs.length & 1 || 2;
  sxs[cs.length-1] = m*cs[cs.length-1];
  for (let i=cs.length-2; i>=0; i--)
    sxs[i] = 2*cs[i] + sxs[i + 1];
  
  let stack = [[0, n, []]];
  let results = [];

  while (stack.length){
    let [i, curr, vs] = stack.pop();

    if (i == cs.length - 1){
      let d = curr / cs[i];

      if (d == ~~d && 
        ((cs.length & 1 && d < 10) || ((!(cs.length & 1) || cs.length == 1) && d < 19)))
        results.push(vs.concat('x'));
      continue;
    }
    
    t = 2;
    curr -= t*cs[i];
    stack.push([
      i + 1, curr,
      vs.slice().concat(t)]);
    
    while (curr >= sxs[i + 1]){
      curr -= cs[i];
      stack.push([
        i + 1, curr,
        vs.slice().concat(++t)]);
    }
  }
  let time = new Date - start;
  return [!!results.length, (time) + 'ms', cs, results];
}

let ns = [
  22, 121, 42,
  66666,
  777777,
  8888888,
  99999999,
  68685,
  68686]

for (let n of ns)
  console.log(n, JSON.stringify(f(n)));

Answer 4

The requirement does not includes returning every possible combination of matched "special numbers", only that a match is found.

const isSpecialInteger = arr => {
  // `arr`: `Array`
  // result, initialized to `0`
  let res = 0; 
  // iterate input `arr`
  for (let n of arr) {
    // divide `n` by `2`
    const c = n / 2;
    // check if `n` is an integer or decimal
    // if decimal subtract decimal portion of 1st divided decimal
    // add decimal portion to 2nd portion of divided decimal
    // else set `x`, `y` to even division of input `n`
    let [x, y] = !Number.isInteger(c) ? [c - (c % 10), c + (c % 10)] : [c, c];
    // set label for `for` loop
    // decrement result of `Math.max(x, y)` 
    N: for (let i = Math.max(x, y); i; i--) {
      // check if `i` converted to
      // string, then array reveresed
      // if equal to `n`
      // if `true` increment `res` by `1` `break` `N` loop
      if (i + +[...`${i}`].reverse().join`` === n) {
        res+= 1;
        break N;
      } 
    }
  }
  // return positive integer or `0`
  return res;
}

console.log(
  isSpecialInteger([22, 121])
);

Answer 5

In the stress and the hurry of an interview, I would have certainly found a dumb and naive solution.

pseudo code

loop that array containing the numbers
    Looping from nb = 0 to (*the number to test* / 2)
        convert nb to string and reverse the order of that string (ie : if you get "29", transform it to "92")
        convert back the string to a nb2
        if (nb + nb2 == *the number to test*)
            this number is special. Store it in the result array
    end loop
end loop
print the result array

function IsNumberSpecial(input)
{
    for (let nb1 = 0; nb1 <= (input / 2); ++nb1)
    {
        let nb2 = parseInt(("" + nb1).split("").reverse().join("")); // get the reverse number
        if (nb2 + nb1 == input)
        {
           console.log(nb1 + " + " + nb2 + " = " + input);
            return (true);
        }
    }
    return (false);
}

let arr = [22, 121, 42];

let len = arr.length;
let result = 0;

for (let i = 0; i < len; ++i)
{
    if (IsNumberSpecial(arr[i]))
        ++result;
}

console.log(result + " number" + ((result > 1) ? "s" : "") + " found");

Answer 6

My JS variant:

const reverseInt = (n) =>
    parseInt(n.toString().split('').reverse().join(''))

const checkSpecialInt = (n) =>{
    for(let i=1;i<=n;i++){
        if (i+reverseInt(i)==n) return true;
    }
    return false;
}
const checkSpecialIntArray = (arr) => 
    arr.filter((e,i)=>checkSpecialInt(e)).length;

let test = [122, 121, 22, 21];
console.log(checkSpecialIntArray(test));

Answer 7

Some pseudo code?

num_special = 0

for item in array:
  for num in range(1, total):
    if num + int(string(num).reversed()) == item
      num_special += 1
      break

print(num_special)

EDIT:

Here's a working Python example:

array = [22, 121]

num_special = 0

for item in array:
  for num in range(1, item):
    if (num + int(str(num)[::-1]) == item):
      num_special += 1
      break

print(num_special)

https://repl.it/repls/UsedLovelyCategory

Answer 8

Here's a rather naïve solution in pseudocode for determining if a number is 'special':

Given an number N (assumed to be an integer)
Let I = Floor(N / 2)
Let J = Ceil(N / 2)
While (I > 0)
    If I is the reverse of J Then
        Return True
    End
    I <- I - 1
    J <- J + 1
End
Return False

A quick JS implementation:

function isSpecial(n) {
  for (var i = Math.floor(n / 2), j = Math.ceil(n / 2); i > 0; i--, j++) {
    console.info(`checking ${i} + ${j}`);
    if (i.toString().split('').reverse().join('') === j.toString())
      return true;
  }

  return false;
}

console.log(isSpecial(121));

I'll leave it up to the you implement the function to count the special numbers in the array. This could be made more efficient by improving the rather crude method for checking for string reversals or possibly by more intelligently skipping numbers.