Eating the tasty numbers!

Computer Science Level 2

Given a positive integer $(1,2,3,\ldots$ ), we start $\color{#3D99F6}{\text{eating the number}}$ from either left or right i.e. we start removing its digits one by one from left to right, or from right to left.

We define a set $\color{#3D99F6}{\text{dish}}$ of the number, which is obtained by noting the number formed after eating every digit (The original number is also included) .

The $\color{#3D99F6}{\text{taste}}$ of a number is sum of all numbers in that number's dish.

What is the smallest non-palindromic number which when eaten from left gives same taste as eating from right?

Details and Assumptions :

The dish of a number can be obtained in 2 ways, either eating from left or eating from right and hence there'll be 2 tastes for each number (maybe the same, that's where you count the number!)
Example of a dish, dish of the number 12635 as eaten from left will be $\{12635,2635,635,35,5\}$ and its dish when eaten from right will be $\{12635,1263,126,12,1\}$
Taste of the number 123 will be $123+23+3 = 149$ from left and it will be $123+12+1 = 136$ from right.
A non-palindromic number is the one which is not the same when read from left or from right, e.g. $12321 , 22 , 1441, 8$ are some examples of palindromic numbers, whereas $98,234,239478$ are some non-palindromic numbers.

The answer is 2170.

12 solutions

Brock Brown
May 31, 2015

Python 2.7:

def palindrome(n):
    return str(n) == str(n)[::-1]
def taste_same(n):
    s = str(n)
    right_taste = n
    left_taste = n
    for bite in xrange(1, len(s)):
        right_taste += int(s[:-bite])
        left_taste += int(s[bite:])
    return right_taste == left_taste
def goal(n):
    return not palindrome(n) and taste_same(n)
n = 0
while not goal(n):
    n += 1
print "Answer:", n

Arulx Z
Jun 7, 2015

public static void main (String[] args){
    for(int n = 10;; n++)
        if(!pal(Integer.toString(n)))
            if(l(n) == r(n))
                System.out.println(n);
}

public static boolean pal(String n) {
    return n.equals(new StringBuilder(n).reverse().toString());
}

private static int r(int n){
    int sum = n;
    for(int i = 0; i < Integer.toString(n).length(); i++){
        n /= 10; sum += n;
    }
    return sum + (n / 10);
}

private static int l(int n){
    int sum = n;
    for(int i = 0; i < Integer.toString(n).length(); i++){
        n = Integer.parseInt(Integer.toString(n).substring(1)); sum += n;
    }
    return sum + (n < 10 ? 0 : Integer.parseInt(Integer.toString(n).substring(1)));
}

Moderator note:

You've managed to write a java solution that's as readable as the python approaches.

Thanks challenge master!

Arulx Z - 5 years, 11 months ago

Do you have any mathematical proof for that..???

jitendra bafna - 5 years, 1 month ago

Proof for what?

Christopher Boo - 5 years ago

When does it stop?

Chris Arsenault - 4 years, 1 month ago

Vincent Miller Moral
Jul 9, 2015

def is_palin(n):
    rev_n = int(str(n)[::-1])
    if n == rev_n:
        return True
    else:
        return False

def taste_from_right(n): #Correct
    ans = n

    while n:
        ans += (n/10)
        n /= 10

    return ans

def taste_from_left(n): #Correct
    ans = n

    i = 1
    while 10**i <= n:
        ans += n%(10**i)
        i += 1

    return ans

num = 10
while True: #Oh sh*t infinite loop
    if not is_palin(num):
        if taste_from_left(num) == taste_from_right(num):
            print num
            break
    num += 1

Roel Baars
Jul 8, 2015

A pure C approach, with simultaneous testing for palindrome and taste.

int SameTaste(int n)
{
    int m = n, p = 0, s = 0, l = 0, r = 0, pw = 1;
    while (m > 0)
    {
        p = p * 10 + m % 10;
        s += pw * (m % 10);
        l += s;
        r += m;
        pw *= 10;
        m = floor(m / 10);
    }
    if (p != n && l == r)
        return 1;
    return 0;
}

int main()
{
    int n = 10;
    while (SameTaste(n) == 0)
        n++;
    printf("%i\n",n);
    return 0;
}

Edited Shorter (but a little more obsfuscated :-) )

Aditya Raut
May 31, 2015

It's quite easy to do by lists, we just write the program to get $\color{#3D99F6}{\text{dish}}$ using strings, this is the way I did...

def dishleft(n):
    """Starts eating the number from left, returns list of all outputs"""
    li=[]
    li.append(''.join(str(n)))
    x=str(n)[1:]
    while x not in li and x!='':
        li.append(x)
        x =str(x)[1:]
    m=[]
    for i in li:
        m.append(int(i))
    return m

def dishright(n):
    """Starts eating the number from right, returns list of all outputs"""
    li=[]
    li.append(''.join(str(n)))
    x=str(n)[:len(str(n))-1]
    while x not in li:
        li.append(x)
        x =str(x)[:len(str(x))-1]
    m=[]
    for i in li:
        if i!='':
            m.append(int(i))
    return m

Now what we do is check if the $\color{#3D99F6}{\text{taste}}$ is same, which is just sum of the elements in lists obtained from above.

So the asked thing will be

li=[]
for n in xrange(10000):
    if sum(dishleft(n))==sum(dishright(n)):
                          li.append(n)

print li

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 111, 222, 333, 444, 555, 666, 777, 888, 999, 1111, 2170, 2222, 3281, 3333, 4392, 4444, 5555, 5607, 6666, 6718, 7777, 7829, 8888, 9999]

It creates this list within a second and then see in the list, smallest non-palindromic one is $\boxed{2170}$

Can't you make your algorithm more efficient? See if you can understand the following:

int taster(long N)//N is the food
    {
    double rev=0,rl=0,lr=0;  
    //'rl' stores right to left taste. 'lr' stores left to right taste
    for(int i=0;N>0;i++,N/=10)
        {
        int dig=N%10;
        rev+=pow(10,i)*dig; 
      //rev stores the reverse of the number in order eaten
        rl+=N;
        lr+=rev;
        }
    return (rl==lr);//returns true if taste is same from both sides
    }

Raghav Vaidyanathan - 6 years ago

If you do write methods using lists, you can use recursion to shorten your code (a single method to return dish that takes two parameters, the number and the direction of eating).

def dish(n,k):
    if n in range(10): return [n]
    if k=='l': return [n]+dish(int(str(n)[1:]),k)  #left eating
    if k=='r': return [n]+dish(int(str(n[:-1])),k)   #right eating

... and then define a method equal_taste() as,

1	`def equal_taste(n): return sum(dish(n,'l'))==sum(dish(n,'r'))`

Prasun Biswas - 5 years, 4 months ago

H. Sch.
Aug 29, 2020

The general conditions on the digits of an (n+1)-digit number $x 0 \dots x n$ is left taste = right taste, ie. $\sum_{k=0}^n k\cdot10^{n-k} x_k = \sum_{k=0}^n x_k\sum_{j=0}^{n-k} 10^j$ . For n=0, the number is trivially palindromic. For n=1, we obtain $10x_0 + 2x_1 = 11x_0 + x_1$ , which reduces to $x_0 - x_1 = 0$ so any 2-digit solution must also be palindromic. For n=2, we need $111x_0 + 11x_1 + x_2 = 100x_0 + 20x_1 + 3x_2$ , which requires $11x_0 - 9x_1 - 2x_2$ . This has nonpalindromic solutions, but only when one of the digits is larger than 9, which is also forbidden. So we need to consider n=3. Here we have $1111x_0 + 111x_1 + 11x_2 + x_3 = 1000x_0 + 200x_1 + 30x_2 + 4x_3$ , whereby we obtain $111x_0 - 89x_1 - 19x_2 - 3x_3$ . Finally, after a little testing a nontrivial solution can be found by $x_0 = 2, x_1 = 1, x_2 = 7, x_3 = 0$ .

Jim Clark
Jan 30, 2017

A perl solution. Could probably be made 'nicer'

sub ftaste {
  (my $num) = @_;
  my $taste = 0;
  my $length = length $num;
  for (my $x=0;$x<$length;$x++) {
    $taste += substr ($num, $x);
  }
  return $taste;
}

sub rtaste {
  (my $num) = @_;
  my $taste = 0;
  my $length = length $num;
  for (my $x=1;$x<=$length;$x++) {
    $taste += substr ($num, 0, $x);
  }
  return $taste;
}

my $natural = 1;
my $found = 0;

while ( $found == 0 ) {
  if ( $natural != reverse $natural and ftaste($natural) == rtaste($natural) ) {
    $found = 1;
  }
  else {
    $natural ++;
  }
}

print "Smallest non palindromic natural number with equal tastes is $natural\n";

Christopher Boo
Jun 3, 2016

Removing its digits one by one can be done mathematically, but python's string library is more convenient and provide more readability. Thus, I implemented all three functions below with first taking in an int parameter then convert it to a string . Look how intuitive it got after that!

def eat_from_left(x):
    x = str(x)
    val = 0
    while x != "":
        val += int(x)
        x = x[1:]
    return val

def eat_from_right(x):
    x = str(x)
    val = 0
    while x != "":
        val += int(x)
        x = x[:-1]
    return val

def is_palindrome(x):
    x = str(x)
    return x == x[::-1]

num = 1
while eat_from_left(num) != eat_from_right(num) or is_palindrome(num):
    num += 1

print num

Bill Bell
Oct 16, 2015

No effort expended for efficiency, yet it provides the answer quickly.

def equalTaste(n):
    if str(n)==str(n)[::-1]:
        return False
    left=list(str(n))
    right=list(str(n))
    totalLeft=0
    totalRight=0
    for i in range(len(left)):
        totalLeft+=int(''.join(left))
        totalRight+=int(''.join(right))
        left.pop()
        right.pop(0)
    if totalLeft==totalRight:
        return totalRight
    else:
        return False

N=1
while True:
    N+=1
    if equalTaste(N):
        print N
        break

Arkin Dharawat
Aug 29, 2015

This is my solution in python

def Dish(N):
D=[]
sumM1=0
sumM2=0
for i in str(N):
    D.append(int(i))
check=0
for i in range(1,len(D)+1):
    n=len(D)-(i-1)
    M1=( D[n-1] * (n))
    M2=sum(D[i]  for i in range(0,n))
    sumM1=sumM1 + (M1 * (10** (i-1)))
    sumM2=sumM2 + (M2 * (10** (i-1)))
if sumM1 ==sumM2:
    return True

for N in range(1000,10000):
    if Dish(N):
        print N

Looking at the numbers printed by the above code ,We can easily see the first non-palindrome which is $\boxed{1270}$ .

Brian Riccardi
Jun 1, 2015

If someone wants a C++ solution, here's mine:

#include<bits/stdc++.h>
using namespace std;

bool isPal(int n)
{
    string s=to_string(n);
    int len=s.length();
    for(int x=0; x<len/2; ++x)
        if(s[x]!=s[len-1-x])
            return false;
    return true;
}

bool solve(int n)
{
    if(isPal(n)) return false;

    int num=0, po=1, tastyL=0, tastyR=n;

    while(n){
        num += po*(n%10);
        po *= 10;
        n /= 10;
        tastyR += n;
        tastyL += num;
    }

    return (tastyL == tastyR);
}

int main()
{
    ios_base::sync_with_stdio(false);

    int n=0;
    while(!solve(n)) ++n;

    cout << n << "\n";

    return 0;
}

Arjun Rana
Jun 1, 2015

Brute force is sufficient to solve this problem. Here's is my Java code for this problem :-

boolean check(int num){
String x = Integer.toString(num);
if(x.equals(new StringBuilder(x).reverse().toString())) return false;
int gum = Integer.parseInt(x);
int sum = Integer.parseInt(x);
for(int i=1;i<x.length();i++){
gum += Integer.parseInt(x.substring(i,x.length()));
sum += Integer.parseInt(x.substring(0, x.length()-i));
}
if(gum == sum) return true;
else return false;
}

Eating the tasty numbers!

The answer is 2170.

12 solutions

Moderator note:

0 pending reports