Amazon Interview Question
Country: United States
How are you keeping track of whether a digit is used or not? Don't you need a hash map here?
#include<iostream>
using namespace std;
void print(int a[],int prev_no ,int index,int inc[]); //
int main()
{
int a[9]={1,2,3,4,5,6,7,8,9};
int inc[9]={0}; // this will take care of which no has been already used
print(a,0,1,inc);
system("pause");
}
void print(int a[],int prev_no ,int index,int inc[])
{
if(index==10) // if index is 10 means 9 digits with given constraint has been formed
cout<<prev_no<<endl;
for(int i=0;i<9;i++) // one by one check whole no at this index
{
if(inc[i]==0)
{
inc[i]=1; //use this no
int t=( prev_no*10 +a [i] );
if( ( t % index)==0) // divisibility check of this new formed no
{
print(a, t, index+1, inc); //if divisible then check if furthur divisibility can be maintained
}
inc[i]=0; // exclude this no
}
}
}
public class Generate9DigitNumber {
public static void main(String[] s) {
int number = generateNumber(9, "");
String str_num = new Integer(number).toString();
if (str_num.length() != 9) {
System.out.println("Required number not found!");
} else
System.out.println(str_num);
}
static int generateNumber(int digits, String number) {
System.out.println(number);
if (digits == 0)
return Integer.parseInt(number);
else if (digits == 1) {
for (int i = 1; i <= 9; i++) {
String temp = number + i;
Integer temp_int = Integer.parseInt(temp);
if (temp_int % (9 - digits + 1) == 0)
return temp_int;
}
// Rite digit not found
return Integer.parseInt(number);
} else {
for (int i = 1; i <= 9; i++) {
String temp = number + i;
Integer temp_int = Integer.parseInt(temp);
if (temp_int % (9 - digits + 1) == 0) {
return generateNumber(digits - 1, temp);
}
}
return Integer.parseInt(number);
}
}
}
}
The idea is simple: A restricted permutation. Unlike checking all possible permutations of the 9 digits, I follow a strategy in which I only consider those possible options of the digits in the current method call, which satisfy a particular criteria, which is that the digit in current consideration, along with the earlier digits, is divisible by a desired number between 1 and 9.
public class Test {
List<String> numbers=new ArrayList<String>();
public static void main(String args[]){
Test test=new Test();
test.generateNumber("",1);
test.print();
}
public void print(){
System.out.println("The numbers are:");
for(int l=0;l<this.numbers.size();l++)
System.out.println(""+(l+1)+": "+this.numbers.get(l));
}
public void generateNumber(String str,int mode){
String prevStr=str;
if(str.length()==9){
numbers.add(str);
return;
}
for(int l=1;l<=9;l++){
str+=String.valueOf(l);
if(Integer.parseInt(str)%mode==0)
generateNumber(str,mode+1);
str=prevStr;
}
}
}
The code will generate all possible numbers.The complexity would be n2.
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import SubSequence.MaxAdditionSubSequence;
import Tree.BinarySearchTree;
import Tree.BinaryTree;
import Utility.MaxSubSequence;
public class Test {
List<String> numbers=new ArrayList<String>();
public static void main(String args[]){
Test test=new Test();
test.generateNumber("",1);
test.print();
}
public void print(){
System.out.println("The numbers are:");
for(int l=0;l<this.numbers.size();l++)
System.out.println(""+(l+1)+": "+this.numbers.get(l));
}
public void generateNumber(String str,int mode){
String prevStr=str;
if(str.length()==9){
numbers.add(str);
return;
}
for(int l=1;l<=9;l++){
if(!str.contains(String.valueOf(l))){
str+=String.valueOf(l);
if(Integer.parseInt(str)%mode==0)
generateNumber(str,mode+1);
str=prevStr;
}
}
}
}
A faster way to search such a number.
#include <iostream>
bool div_7(int *d);
void print_num(char *mark, int *d);
int main (int argc, char * const argv[]) {
char * mark=new char [10];
memset(mark, 0, 10);
int d[10];
d[5]=5;
mark[5]=1;
for (int i_78=16; i_78<100; i_78+=8)
if (i_78%10!=0&&i_78!=88&&i_78!=56)
{
d[7]=i_78/10;
d[8]=i_78%10;
mark[d[7]]=1;
mark[d[8]]=1;
for (int i_34=12;i_34<100;i_34+=4)
if (i_34%10!=0&&i_34!=44&&i_34!=88)
{
d[3]=i_34/10;
d[4]=i_34%10;
if (mark[d[3]]||mark[d[4]]) continue;
mark[d[3]]=1;
mark[d[4]]=1;
for (int i_2=2;i_2<10;i_2+=2)
if (!mark[i_2])
{
d[2]=i_2;
mark[i_2]=1;
for (int i_1=1;i_1<10;i_1++)
if (!mark[i_1]&&
(i_1+d[2]+d[3])%3==0)
{
d[1]=i_1;
mark[i_1]=1;
for (int i_6=1;i_6<10;i_6++)
if (!mark[i_6])
{
d[6]=i_6;
mark[i_6]=1;
if (div_7(d))
{
print_num(mark, d);
}
mark[i_6]=0;
}
mark[i_1]=0;
}
mark[i_2]=0;
}
mark[d[3]]=0;
mark[d[4]]=0;
}
mark[d[7]]=0;
mark[d[8]]=0;
}
return 0;
}
bool div_7(int *d)
{
int t=0;
int t_1=0;
for (int i=1;i<=7;i++)
{
t=(t*10+d[i]);
if (i<=6)
t_1=(t_1*10+d[i]);
}
if (t%7==0&&t_1%6==0) return true;
return false;
}
void print_num(char *mark, int *d)
{
for (int i=1;i<=8;i++)
std::cout<<d[i];
for (int i=1;i<10;i++)
if (!mark[i])
std::cout<<i<<"\n";
}
If the given numbers are 1-9 then looks like there is no solution for this. Divisiblity rule of 2 says, the first digit must be an even number (2,4,6,8) and divisibility rule of 5 says the first should be either 0 or 5. Zero (0) is not part given numbers and 5 can't be the first digit. So no solution. If the given set 0-9, then we may have one. Working on it :)
If the set is 0-9 then, its too easy to find out 10 digit number which meets the above condition. 1987654320.
@Ashok,
first 3 digits "320" are not divisible by 3 (for right to left)
if you consider left to right then "19" is not divisble by 2.....Can you check simple test case before posting?
Sorry guys.. Mis-understood the question. It says first 3, but I read it as 1st and 3. But I believe the my first comment will still be valid??
Initial case:
xxxx xxxx x
First 9 digits must be div by 9. 1-8 are not div by 9. If we choose 9, then 2nd dig is not div by 9. 0 is not allowed. Hence, this problem does not have a solution by counter-example.
- Jim August 12, 2012public class NineDigitNumber { public static boolean findTheNum(long num, int[] digits, int index) { if (index == digits.length - 1) { num = num * 10 + digits[index]; System.out.println(num); return true; } for (int i = index; i < digits.length; i = i + 2) { swap(digits, index, i); long nextNum = num * 10 + digits[index]; if (nextNum % (index + 1) == 0) { if (findTheNum(nextNum, digits, index + 1)) { return true; } } swap(digits, index, i); } return false; } private static void swap(int[] digits, int i, int j) { int temp = digits[i]; digits[i] = digits[j]; digits[j] = temp; } public static void main(String[] args) { int[] digits = {1, 2, 3, 4, 5, 6, 7, 8, 9}; findTheNum(0, digits, 0); } }