Deshaw Inc Interview Question Software Engineer / Developers
I think this is the algorithm to do it. I think they just want you to come up with the algorithm. This is a typical permuation algorithm with a few tweaks.
string numberStr = "123456789";
print (numberStr, "");
void print(string numberStr, string result){
if (result.length() >= 9)
{
cout << result << endl;
}
else{
for (int i = 0; i < numberStr.length(); ++i)
{
int len = result.length();
char chr = numberStr[i];
int n = (atoi(result) * 10) + atoi(chr);
if ((n%(len + 1)) == 0)
{
result += chr;
remove chr from numberStr
print (numberStr, result);
}
}
}
}
381654729 is the number. This question is part of USA Math Talent Search Problems. You can google it:
http://www.google.com/search?q=381654729
B0Rg on October 23, 2006 is correct. 381654729 is not the only number though. Execute the following program and it will list all such elements
import java.util.*;
public class Selection {
private ArrayList<Integer> WorkingSet = new ArrayList<Integer>();
private ArrayList<Integer> TempSet = new ArrayList<Integer>();
public static void main(String[] args)
{
Selection sel = new Selection();
sel.getTheNum();
}
public void getTheNum()
{
this.WorkingSet.add(1);
this.WorkingSet.add(2);
this.WorkingSet.add(3);
this.WorkingSet.add(4);
this.WorkingSet.add(5);
this.WorkingSet.add(6);
this.WorkingSet.add(7);
this.WorkingSet.add(8);
this.WorkingSet.add(9);
try
{
for (int i = 2; i <= 9; i++)
{
Iterator<Integer> iter = this.WorkingSet.iterator();
System.out.println("Elements after iteration no-" + i + " " + WorkingSet.toString());
Thread.sleep(2000);
while(iter.hasNext())
{
Integer num = iter.next();
num *= 10;
for (int j = 1; j <= 9; j++)
{
num += j;
if ((num % i) == 0)
this.TempSet.add(num);
num -= j;
}
}
this.WorkingSet.clear();
this.WorkingSet.addAll(TempSet);
this.TempSet.clear();
}
System.out.println("Elements after last iteration no-" + WorkingSet.toString());
}
catch(InterruptedException ie)
{
}
}
}
B0Rg on October 23, 2006 is correct. 381654729 is not the only number though. Execute the following program and it will list all such elements
import java.util.*;
public class Selection {
private ArrayList<Integer> WorkingSet = new ArrayList<Integer>();
private ArrayList<Integer> TempSet = new ArrayList<Integer>();
public static void main(String[] args)
{
Selection sel = new Selection();
sel.getTheNum();
}
public void getTheNum()
{
this.WorkingSet.add(1);
this.WorkingSet.add(2);
this.WorkingSet.add(3);
this.WorkingSet.add(4);
this.WorkingSet.add(5);
this.WorkingSet.add(6);
this.WorkingSet.add(7);
this.WorkingSet.add(8);
this.WorkingSet.add(9);
try
{
for (int i = 2; i <= 9; i++)
{
Iterator<Integer> iter = this.WorkingSet.iterator();
System.out.println("Elements after iteration no-" + i + " " + WorkingSet.toString());
Thread.sleep(2000);
while(iter.hasNext())
{
Integer num = iter.next();
num *= 10;
for (int j = 1; j <= 9; j++)
{
num += j;
if ((num % i) == 0)
this.TempSet.add(num);
num -= j;
}
}
this.WorkingSet.clear();
this.WorkingSet.addAll(TempSet);
this.TempSet.clear();
}
System.out.println("Elements after last iteration no-" + WorkingSet.toString());
}
catch(InterruptedException ie)
{
}
}
}
#include<iostream>
#include<cstdlib>
#include<cmath>
using namespace std;
bool checknum(char s[],int n)
{
if(s[0]=='0')
return false;
s[n]='\0';
int num=atoi(s);
// cout<<"num ="<<num<<"\n";
//getchar();
bool b[10]={0};
for(int i=n;i>1;i--)
{
if(num%i!=0)
{ //cout<<num<<"not div by "<<i<<"\n";
return false;
}
int r=num%10;
num=num/10;
if(b[r]==1)
return false;
else
b[r]=1;
}
return true;
}
void findnum(char s[],int n)
{
if(n==9)
{ s[n] ='\0';
cout<<s<<"****\n";
return;
}
else
{
for(int i= 0 ; i<10 ; i++ )
{
s[n]='0'+i;
if(checknum(s,n+1))
findnum(s,n+1);
//else
// findnum(s,n);
}
}
}
int main()
{
char s[10]={"100000000"};
findnum(s,0);
return 0;
}
simple recursion if we know for n-1 digit we can get for n digits
public HashMap<Integer,HashSet<Integer>> findPolyDivisibleNumber(int n)
{
HashMap<Integer,HashSet<Integer>> map=new HashMap<Integer,HashSet<Integer>>();
HashSet<Integer> sets;
if(n==1)
{
for(int i=1;i<=9;i++)
{
sets=new HashSet<Integer>();
sets.add(i);
map.put(i, sets);
}
return map;
}
HashMap<Integer,HashSet<Integer>> oldMap=findPolyDivisibleNumber(n-1);
Set<Integer> old=oldMap.keySet();
Iterator<Integer> itr=old.iterator();
while(itr.hasNext())
{
int temp=itr.next();
HashSet<Integer> set=oldMap.get(temp);
HashSet<Integer> setRes;
for(int i=1;i<=9;i++)
{
if((temp*10+i)%n==0 && !set.contains(i))
{
setRes=new HashSet<Integer>();
setRes.add(i);
setRes.addAll(set);
map.put(temp*10+i,setRes);
}
}
}
return map;
}
static void FindNumbers(String result, String numberStr) {
int len = numberStr.length();
if (result.length() >= 9) {
System.out.println(result);
}
else {
for (int i = 0; i < numberStr.length(); i++) {
int nlen = result.length();
if (Integer.parseInt(result + numberStr.charAt(i)) % (nlen + 1) == 0)
FindNumbers(result + numberStr.charAt(i), numberStr.substring(0, i) + numberStr.substring(i + 1, len));
}
}
}
I dont think such a number will exist. According to the problem definition the numbered formed by first two digits must be divisible by 2 and and the number formed by the first five digits must be divisible by 5. Only case it can happen is first digit must be a zero which should not be the case according to problem statement.
- kapil August 15, 2006Well if my understanding of the problem is wrong please correct me.