Google Interview Question
Testing / Quality AssurancesIf any number in between that range contains 0 as its last digit ignore all those. Because it will all generate atleast 2 zeros when we square it.
Same idea as mine.
And I think we should clarify the following assumption with interviewer first:
(Assumption) '0' can't be the leading digit
The following is the Java implementation:
class G214
{
public static void main(String[] args)
{
System.out.println("firstPerfectSquare10digits: " + firstPerfectSquare10digits());
}
public static long firstPerfectSquare10digits()
{
for (long i = 31991; i <= 99380; i++)
{
boolean[] used = new boolean[10];
for (char c : ((i * i) + "").toCharArray())
{
used[c - '0'] = true;
}
boolean ok = true;
for (boolean b : used) if (!b) {ok = false; break;}
if (ok) {return (i * i);}
}
return (-1);
}
}
this problem can be solve efficiently using bisection method,
> if a number is n digit number then its squareroot must be of n/2 digit,
> take low=1 and hight =n/2 digit largest number
> find the mid=(low+high)/2
>if mid^2== number return
> if mid^ 2> number then high=mid-1
>else low=mid+1
>repeat above process recursively untill low>high
this gives solution in (log n) time
please tell me if I m' wrong..!!!
Thnx
this problem can be solve efficiently using bisection method,
> if a number is n digit number then its squareroot must be of n/2 digit,
> take low=1 and hight =n/2 digit largest number
> find the mid=(low+high)/2
>if mid^2== number return
> if mid^ 2> number then high=mid-1
>else low=mid+1
>repeat above process recursively untill low>high
this gives solution in (log n) time
please tell me if I m' wrong..!!!
Thnx
Get the number of digits. Say n
High = Int(Sqrt(pow(n, 10)-1))
Low = Int(Sqrt(pow(n-1, 10)))+1
So the number will be in between Sqr(Low) and Sqr(high)
And the sum of digits should be 45
Sum to 45 is wrong. Cos there can be sequence with repeated digits which can sum to 45
If i were to do it in Mathematica, this would be the solution. I am not sure if these methods are there in any programming APIs. Let me know if you know of any.
Given number of digits n...
Length[Union[IntegerDigits[m^2]]] == n,
Print["Number = ", m^2]],
{m, Floor[Sqrt[pow(10, n-1)]], Floor[Sqrt[pow(10, n)]]}];
this can be done by simple mathematical approach
where in we create a loop of 10 digits no. with non repeated digits (simple P& C)
and check their square roots are float or int and if it is int then it will be shown as out put.
I made a mistake in the above answer, should be:
int num = 1;
while ( num has less than 10 digits){
num = num << 2; //equivalent of multiple by 4
}
Basically this algorithm is checking to see if 2^0, 2^2, 2^4, 2^6....2^n, where n is even is a perfect square root of 10 digits. Note that 2^n is always perfect square root.
The question only ask you to find a number of 10 digit with perfect square root, it didn't ask you to find the First perfect square root, so you can use bitwise operation to emulate 2 to the power of 2s to obtain a very efficient solution.
Also note that the above algorithm will always find a number with 10 digits because if you multiple X by 4, that X can grow maximum 1 digit (think about 99999*4).
while ( num has less than 10 digits){
num = num << 2; //equivalent of multiple by 4
} this is the psuedo code lol, it's using bitwise operation to get power of 2s.
Think about this:
2^0=1, 2^2=4, 2^4=16, 2^6=64, 2^8=256 are all perfect squares. Now, think about the binary representation of these number:
1=0000000001, 4=0000000100, 16=000010000, 64=001000000, 256=100000000
See the pattern? I'm just trying to shift the only 1 in the binary number to the left by 2 positions each time, and each time I do that the resulting number in base 10 representation is always a perfect square.
So the idea is to keep shifting until you get a number with 10 digits.
Pls READ question first. If you DON'T understand the question ask someone to clarify (before attempting to respond). In a real interview you might give answer instantly without even understanding the question first.
The question asks "10 digit number such that the number has all of [0,9] digit, i.e. NO REPEAT"
Start with smallest 10 digit number:
1. Find the sum of digits of the number
2. If the sum can be expressed as the sum of odd numbers like, sum = 1+3+5+7+....,
then it is a perfect square.
3. Else increment the number by 1.
Use loop with base as smallest 10 digit number and limit as largest one, with an increment of 1 at each iteration (this may not be needed)
how many perfect squares are there in 100 is sqrt(100)!!!
sqrt(9876543210) - sqrt(1023456789)
as lower limit = sqrt(1023456789)
upper limit = sqrt(9876543210);
loop i in lower to upper
if(sqr(i) == all distince digit)cnt++;
can anyone have better idea
above solution by GekkoGordan looks good. because calculating square is much much faster than sqrt.
for this problem with squares o/p comes with in 1 second.... with sqrt it is taking more than 5 mins
There is a better idea - because we know that the sum of all the digits of the (10 digit) number is 45 - its divisible by 9, therefore the square root of that number is divisible by 3. Hence we dont have to square each number to find the solution, only square the multiples of 3 to find the solution. So the max numbers that you will have to square to arrive at the solution will be reduced from 67k to 23k.
public class perfectSquare {
/**
* @param args
*/
public static int check(long num)
{
int[] A={0,0,0,0,0,0,0,0,0,0};
int i;
while ( num != 0)
{
i=(int) (num%10);
if (A[i]==0)
{
A[i]=1;
num=num/10;
}
else
return 0;
}
return 1;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
//int b= (int)Math.sqrt(1000000000);
long b=(long) Math.sqrt(1000000000);
long bn= 99999999999L;
long e=(long) Math.sqrt(bn);
int count=0;
for (long j=b;j<=e;j++)
if(check((long)(j*j))!=0)
{
count++;
System.out.println((j*j));
}
System.out.println("count::"+count);
}
}
public class perfectSquare {
/**
* @param args
*/
public static int check(long num)
{
int[] A={0,0,0,0,0,0,0,0,0,0};
int i;
while ( num != 0)
{
i=(int) (num%10);
if (A[i]==0)
{
A[i]=1;
num=num/10;
}
else
return 0;
}
return 1;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
long b=(long) Math.sqrt(1023456789);
long bn= 9876543210L;
long e=(long) Math.sqrt(bn);
int count=0;
for (long j=b;j<=e;j++)
if(check((long)(j*j))!=0)
{
count++;
System.out.println((j*j));
}
System.out.println("count::"+count);
}
}
public class perfectSquare {
/**
* @param args
*/
public static int check(long num)
{
int[] A={0,0,0,0,0,0,0,0,0,0};
int i;
while ( num != 0)
{
i=(int) (num%10);
if (A[i]==0)
{
A[i]=1;
num=num/10;
}
else
return 0;
}
return 1;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
long b=(long) Math.sqrt(1023456789);
long bn= 9876543210L;
long e=(long) Math.sqrt(bn);
int count=0;
for (long j=b;j<=e;j++)
if(check((long)(j*j))!=0)
{
count++;
System.out.println((j*j));
}
System.out.println("count::"+count);
}
}
One line solution in Python. 87 such solution exists. Start from 0 to 10^5. Check if the square contains all unique digit from 0-9, best way is to put in a set and check whether length is 10.
>>> [i for i in range(99999) if len(set(str(i**2))) == 10]
[32043, 32286, 33144, 35172, 35337, 35757, 35853, 37176, 37905, 38772, 39147, 39336, 40545, 42744, 43902, 44016, 45567, 45624, 46587, 48852, 49314, 49353, 50706, 53976, 54918, 55446, 55524, 55581, 55626, 56532, 57321, 58413, 58455, 58554, 59403, 60984, 61575, 61866, 62679, 62961, 63051, 63129, 65634, 65637, 66105, 66276, 67677, 68763, 68781, 69513, 71433, 72621, 75759, 76047, 76182, 77346, 78072, 78453, 80361, 80445, 81222, 81945, 83919, 84648, 85353, 85743, 85803, 86073, 87639, 88623, 89079, 89145, 89355, 89523, 90144, 90153, 90198, 91248, 91605, 92214, 94695, 95154, 96702, 97779, 98055, 98802, 99066]
>>> len([i for i in range(99999) if len(set(str(i**2))) == 10])
87
this works... but dunno if this is the optimal...
-----------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
void permute(char *a, int start, int end)
{
static int found = 0;
int idx = 0;
char tmp;
if(found == 0)
{
if(start == end)
{
long int number = strtol(a, NULL, 0);
float sqrtno = sqrt(number);
if((pow(sqrtno,2) - number)== 0)
{
printf("The 10 digit number is %ld is a perfect square and the square root is %f\n", number,sqrtno);
found = 1;
}
else
{
printf("The 10 digit number is %ld is not a perfect square\n", number);
}
}
else
{
for(idx = start; idx <= end; idx++)
{
tmp = a[start];
a[start] = a[idx];
a[idx] = tmp;
permute(a, start+1, end);
tmp = a[start];
a[start] = a[idx];
a[idx] = tmp;
}
}
}
}
int main()
{
char a[] = "1234567890";
permute(a, 0, strlen(a) - 1);
}
Similar to the previous, I believe.
Find the 10 digit permutations. There are 10! permutations, but this is still much smaller than roughly 10^10 10 digit numbers.
Check each to see if they are a perfect square
digits = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
import math
def isPerfectSquare(num):
s = math.sqrt(num)
i = int(s)
if ( (i*i) == num):
return True
else:
return False
def permute(soFar, remaining):
if not remaining:
num = 0
for d in soFar:
num = num * 10 + d
if isPerfectSquare(num):
print num
return
for r in remaining:
rem = [x for x in remaining if x != r]
sf = soFar + [r]
permute(sf, rem)
permute([], digits)
//C# code
class Program
{
static bool check(long num)
{
sbyte[] mas = { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 };
sbyte temp = 0;
while (num != 0)
{
temp=(sbyte)(num % 10);
if (mas[temp] == temp)
return false;
mas[temp] = temp;
num /= 10;
}
return true;
}
static void Main(string[] args)
{
long n, min = 31990, max = 99381;//sqrt(1023456789) and sqrt(9876543210)
for (long i = min; i <= max; ++i)
{
n=i*i;
if(check(n))
Console.WriteLine("num = {0}, i = {1}", n, i);
}
Console.ReadKey();
}
}
import java.lang.*;
import java.util.*;
public class GoogTest{
public static void main(String[] args)
{
long startNum = 31991;
long endNum = 99381;
for(long i=startNum; i<=endNum; i++){
if(findRepeat(i)){
System.out.println("I is "+ i);
System.out.println(i * i);
}
}
}
public static boolean findRepeat(long n){
long nsq = n * n;
String num = Long.toString(nsq);
boolean flag = false;
ArrayList<Long> hm = new ArrayList<Long>();
int m=0;
for(int j=0; j< num.length(); j++){
long r = nsq % 10 ;
nsq/= 10;
if(!(hm.contains(r))){
hm.add(r);
m++;
}
}
if(m == num.length()) {
return true;
}else{
return false;
}
}
}
Why don't we use the basic mathematical way to find if a number is a perfect square or not.
The code below illustrates that:
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
void findNearest(char s[], char q[])
{
char s1[20];
int t = atoi(s);
cout << t << endl;
int val;
int x, y, xVal;
int temp;
for(int i = 0; i < 10; i++)
{
if(q[0] != '\0')
{
sprintf(s1, "%s%d", q, i);
x = atoi(s1) ;
}
else
{
x = i;
}
y = x * i;
if(y <= t)
{
val = y;
temp = i;
xVal = x;
}
}
sprintf(q, "%d", xVal + temp);
y = t - val;
sprintf(s,"%d",y);
}
bool PerfectSquare(char s[])
{
int l = strlen(s);
char s1[20];
char q[10];
q[0] = '\0';
if(l == 0) return false;
for(int i = 0; i < l;)
{
if( l % 2 != 0 && i == 0)
{
sprintf(s1, "%c", s[i]);
i++;
}
else
{
if(i == 0)
sprintf(s1, "%c%c", s[i], s[i+1]);
else
sprintf(s1, "%s%c%c", s1, s[i], s[i+1]);
i+=2;
}
findNearest(s1, q);
}
int x = atoi(s1);
if(x != 0)
return false;
return true;
}
int main(void)
{
char s[20];
cin >> s;
if(PerfectSquare(s))
cout << "True" << endl;
else
cout << "False" << endl;
return 0;
}
int i; // assume i is 64 bit.
for ( i = 100000; pow(i,2) < 9,999,999,999; i++) {
cout<< Pow(i,2);
}
I think:
1. compute: sqrt(1000000000) = 31622.78 and sqrt(9000000000) = 94868.33;
2. from 31623 to 94868:
first compute the squire of every integer between this range;
check if the value is non repeated 10 digits, if yes, then put it in an array.
3. The result is the array
The total times of computation equals to 94868 - 31623 = 63245.
The smallest number with 10 digits will be 1023456789 and largest will be 9876543210
Start from any one number form these two..rotate right once only if 0 is not the leading digit and perform square root on it..if it an integer then that is the answer...hardly 9 rotations will be required
-We need to find a number that is 10 digits long with non repeats, that means it has to be a permutations of the '0123456789' sequence.
-In python we use itertools.permutations to generate an iterable of all possible permutations of that sequence.
-Next we iterate through each element, convert it to an int (itertools.permutations iterables in form of tuples) and check wether it is a perfect square or not. For that we can write a small function that we can invoke to check in the form of : return int(sqrt(x))**2 == x
public class TenDigitNumPerfSquare {
public static void main(String args[]){
long i;
boolean m=false;
TenDigitNumPerfSquare t=new TenDigitNumPerfSquare();
for(i=1000014128;i<9999999999L;i++){
if(Math.sqrt(i)==Math.round(Math.sqrt(i))){
m=t.good(i);
}
if (m==true){
break;}
}
System.out.println("The number is" +i);
}
boolean good(long i){
long num1L=i;
boolean re;
int count=0;
int len=Long.toString(i).length();
int[] arr=new int[len];
for (int y=0;y<len;y++){
arr[y]=(int)(num1L%10);
num1L=num1L/10;
}
for (int x=0;x<len;x++){
for(int j=x+1;j<=len-1;j++){
if (arr[x]==arr[j]){
count++;
break;
}}
}
if(count==0){
return true;
}else
return false;
}
}
10 digits (non repeated digits): Does that mean using all 0-9 digits.
- GekkoGordan February 20, 2011So basically find a number which is a perfect square that contains all digits without repetitions?
So why not just check all squares of numbers from sqrt(1023456789) to sqrt(9876543210)
i.e. check if squares of numbers from 31991 to 99380 contain any repetitions.