Flipkart Interview Question
SDE-2sCountry: India
Interview Type: In-Person
Follow the link oeis.org/A006886 you will find the definition:
Kaprekar numbers: n such that:
n=q+r and n^2=q*10^m+r,
for some m >= 1, q>=0 and 0<=r<10^m,
with n != 10^a, a>=1
For example: n = 297 is a Kaprekar because (q = 88, m = 3, r = 209)
297^2 = 88209 = 88*10^3 + 209
and
297 = 88 + 209;
First 10 Kaprekar numbers are:
1, 9, 45, 55, 99, 297, 703, 999, 2223, 2728
I can prove that if n is a Kaprekar number then n % 9 is either 0 or 1, as follow:
Let k = n % 9. Then (n^2) % 9 == (k^2) % 9;
Since n^2 =q*10^m+r, for some m >= 1, q>=0 and 0<=r<10^m, we have
(k^2) % 9 = (n^2) % 9
= (q*10^m+r) % 9
= (q%9 * 10^m % 9 + r%9) %9
= (q%9 + r%9) % 9
= (q+r) %9
= n%9
= k
Thus: (k^2) % 9 = k
This happens only with k = 0 or 1.
Thus, if n is a Kaprekar number, then n%9 will be either 0 or 1.
Folks, don't forget the base in Kaprekar's definition.
import math
def kaprekar(n, base):
#for x in range(0, int(math.sqrt(n))+1):
for x in range(0, n+1):
ax = x*x
blen = 0
b = 0
while ax > base:
b += ax % base * (base**blen)
ax /= base
if b>0 and ax + b == x:
print x, "=", ax, "+", b, "; ", x,"**2=", x*x
break
blen = blen + 1
kaprekar(1000000, 10)
namespace ConsoleApplication12
{
class Program
{
static void Main(string[] args)
{
int count = 1;
do
{
int b = count * count;
int c, d, e;
if (count < 10)
{
c = b / 10;
d = b % 10;
e = c + d;
if (e == count)
Console.WriteLine("true {0}",count);
}
else if (count > 10 && count < 100)
{
c = b / 100;
d = b % 100;
e = c + d;
if (e == count)
Console.WriteLine("true {0}",count);
}
count++;
} while (count < 100);
Console.ReadKey();
}
}
}
Interesting!
- ninhnnsoc April 27, 2014Let X be a Kaprekar number. Let s(X) = sum of digits of X, recursively.
For example,
s(9) = 9;
s(703) = s(7+0+3) = s(10) = s(1+0) = 1; ...
I found that for all Kaprekar number X from 1 to 10^51, s(X) is either 1 or 9.
It means that (X % 9) will be 1 or 0.
This will speed up your search significantly!