Epic Systems Interview Question
Country: United States
Interview Type: Written Test
Thanks for this. I got an idea to get started with this problem because of this solution. Some improvement suggestions -
1. This code doesn't work for 24 = 12 * 1 * 2. This is because your seed stops looping at value 11. Just change it to seed <= (num * 0.5)
2. Doesn't work for 111 = 111 * 1 * 1 * 1. For this case to be handled, we'll have to expand the loop for seed to loop all the way until num, which is while (seed <= num). Seems inefficient. The other alternative is to somehow check if all digits are ones.
3. We can initially check if num < 10. If yes, then that itself is the seed. Hence we don't need to enter the while loop. This also gives us the flexibility to initialize seed to 10 and start with 10, rather than 1.
check this it works for all inputs
private static void seed(int i) {
ArrayList<Integer> factor=new ArrayList<Integer>();
for(int j=2;j<=i/2;j++){
if(i%j==0)
factor.add(j);
}
int temp=1;
for(int number:factor){
int temp2=number;
temp=number;
while(number>0){
temp*=number%10;
number=number/10;
}
if(temp==i)
System.out.println(temp2);
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author Anubhav Jain
*/
public class Seed {
public static void main(String args[]) throws IOException
{
System.out.println("Enter the number");
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String number = br.readLine();
int num = Integer.parseInt(number);
int i;
for(i=1;i<=num;i++)
{
//System.out.println("*" + i);
int count = 1;
int y=i;
count = count * y;
while(y>=1)
{
count = count * (y%10);
y = y/10;
}
//System.out.println(count);
if(count == num)
{
System.out.println(i);
}
}
}
}
#include<iostream.h>
#include<process.h>
void main()
{
double num;
cout<<"Enter the number : ";
cin>>num;
cout<<"\nThe seeds are : ";
if(num==0)
{
cout<<"All numbers having atleast one digit zero";
exit(0);
}
for(int i=1; i<=num; i++)
{
int n=i;
double s=i;
while(n!=0)
{
int r;
r=n%10;
n=n/10;
s=s*r;
}
if(s==num)
cout<<i<<" ";
}
}
Console.WriteLine("Enter the number");
int X = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Enter another number");
int Y = Convert.ToInt32(Console.ReadLine());
int re,tmp = X,mux=1,mul;
while(tmp > 0)
{
re = tmp % 10;
mux = mux * re;
tmp = tmp / 10;
}
mul = mux * X;
if(mul == Y)
Console.WriteLine("{0} is the seed of {1}",X,Y);
else
Console.WriteLine("{0} is not the seed of {1}",X,Y);
hey anubhav, i was wondering why do you need to initialize count to 1 and y to i and then multiply count by y... can we just not initialie count to i because it would give the same result?
I think the question is about search space elimination. Let given number be n.
Put t = log n.
Say the seed number has digits a0 a1 a2 a3... ai with ai being most significant digit.
[ a0 + 10*a1 + 100 *a2 + (10^i)ai ] * a0 * a1 * a2 ... ai = n
For this to hold, a0 * a1 * a2 * ... * ai <= n/(10^i + ... + 1000 + 100 + 10 +1)
Like this we can get limits on the digits we need to scan through. Solve for each i <= t after narrowing down search space.
import java.io.BufferedReader;
import java.io.Console;
import java.io.InputStreamReader;
public class seed {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int number = 0;
try{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("enter the number");
number = Integer.parseInt(br.readLine());
System.out.println("number is "+number);
}
catch(Exception e){
e.printStackTrace();
}
int seed=0, seed2;
while(seed<=number){
seed2 = seed;
int val = seed;
while(seed>0){
val = val *(seed%10);
seed = seed/10;
}
seed =seed2 + 1;
if(val==number){
System.out.println("seed is "+(seed-1));
}
}
}
}
#include<iostream.h>
#include<process.h>
void main()
{
double num;
cout<<"Enter the number : ";
cin>>num;
cout<<"\nThe seeds are : ";
if(num==0)
{
cout<<"All numbers having atleast one digit zero";
exit(0);
}
for(int i=1; i<=num; i++)
{
int n=i;
double s=i;
while(n!=0)
{
int r;
r=n%10;
n=n/10;
s=s*r;
}
if(s==num)
cout<<i<<" ";
}
}
#include<stdio.h>
#include<conio.h>
void main()
{
int a,n,i=1,count,prod=1,flag=0;
clrscr();
printf("enter number\n") ;
scanf("%d",&n);
printf("All seed numbers of n are:\n");
while(n>0)
{
if(n%i==0)
{
prod=prod*i;
n=n/i;
count=1;
a=n;
while(a>0)
{
count=count*(a%10);
a=a/10;
}
if(count==prod)
{
printf("%d\n",n);
if(i==1)
i++;
}
else if(count!=prod && i==1)
i++;
}
else
i++;
}
}
#include<iostream>
using namespace std;
bool check(int first, int second)
{
int product=1;
while(first != 0)
{
product *= first%10;
first /= 10;
}
return (product==second);
}
int main()
{
int n;
cin>>n;
for(int i=1;i*i<=n;i++)
{
if(n%i == 0)
{
if(check(i,n/i)) cout<<i<<endl;
if(i*i!=n && check(n/i,i)) cout<<n/i<<endl;
}
}
return 0;
}
public class seed {
public static void main(String[] args) {
int num=34;
int seed;
// for(seed=1;seed<=num/2;seed++){
// if(seed*eachnum(seed)==num){
// System.out.println("seed is"+seed);
// }
// }
for(seed=num/2;seed>0;seed--){
if(seed*eachnum(seed)==num){
System.out.println("seed is"+seed);break;
}
}
if(seed==0){
System.out.println("no seed");
}
}
private static int eachnum(int seed) {
int cal=1;
int rest;
rest=seed%10;
seed=seed/10;
if(seed==0){
cal=cal*rest;
}else{
cal=rest*eachnum(seed); }
return cal;
}
}
public class seed {
public static void main(String[] args) {
int num=1716;
int seed;
for(seed=num/2;seed>0;seed--){
if(seed*eachnum(seed)==num){
System.out.println("seed is "+seed);break;
}
}
if(seed==0){
System.out.println("no seed");
}
}
private static int eachnum(int seed) {
int cal=1;
int rest;
rest=seed%10;
seed=seed/10;
if(seed==0){
cal=cal*rest;
}else{
cal=rest*eachnum(seed); }
return cal;
}
}
Python working code.
Just made the loop up to the given number, and mul each individual digits in the i, if product == sum, return i. Intuitive algo, maybe could be improved.
"""
3/19/2013 3:16
@Python 2.7
Find the seed of a number.
Eg : 1716 = 143*1*4*3 =1716 so 143 is the seed of 1716. find all possible seed for a given number.
"""
class FindSeed(object):
def __init__(self, num):
if num is None:
print 'invalid number!!'
raise SystemExit
self._num = int(num)
def findS(self):
result = []
for i in range(self._num):
tmp = str(i)
product = i
for c in tmp:
product *= int(c)
if product == self._num:
result.append(str(i))
if result == []:
return 'No seed found!'
else:
return ', '.join(result)
if __name__ == '__main__':
seed = FindSeed(1716)
print seed.findS()
static ArrayList<Integer> getAllSeeds(int num){
ArrayList<Integer> result=new ArrayList<Integer>();
for(int i=0;i<=num/2;i++){
int sum=i;
String s=String.valueOf(i);
for(int j=0;j<s.length();j++){
sum*=Character.getNumericValue(s.charAt(j));
}
if(sum==num){result.add(i);}
}
return result;
}
import sys
import math
def main():
Seed(171654)
def Seed(a):
for i in range(1,a/2):
multi = 1
if a%i==0:
for j in str(i):
multi = multi * int(j)
multi = multi*i
if(multi == a):
print i
for j in str(a):
multi = multi * int(j)
multi = multi*a
if(multi == a):
print a
if __name__ == '__main__':
main()
import sys
import math
def main():
Seed(171654)
def Seed(a):
for i in range(1,a/2):
multi = 1
if a%i==0:
for j in str(i):
multi = multi * int(j)
multi = multi*i
if(multi == a):
print i
for j in str(a):
multi = multi * int(j)
multi = multi*a
if(multi == a):
print a
if __name__ == '__main__':
main()
public class Seed {
public static void main(String[] args) {
int num = 1716;
//int num=24;
// int num=111;
int product = 1;
int digit;
for (int i = 1; i <= num; i++) {
int factor = i;
product = i;
if (num % factor == 0) {
while (factor >= 1) {
digit = factor % 10;
product = product * digit;
factor=factor/10;
}
}
if (product==num)
System.out.print(i);
}
}
}
import java.util.ArrayList;
class FindSeeds {
public static ArrayList<Integer> getSeeds(int n) {
ArrayList<Integer> res = new ArrayList<Integer>();
for (int i = 1; i <= n; i++) {
if (n % i == 0) {
res.add(i);
}
}
return res;
}
public static void main(String[] args) {
System.out.println(getSeeds(1716));
}
}
#include<stdio.h>
int main()
{
int input;
scanf("%d",&input);
int num=0,num_copy,i,j;
int *digit;
int count_digit_input=0;
int prod;
for(i=0;i<input/2;i++)
{
num=num+1;
prod=num;
num_copy=num;
while(num!=0)
{
num=num/10;
++count_digit_input;
}
digit=(int*)malloc(count_digit_input*sizeof(int));
num=num_copy;
for(j=0;j<count_digit_input;j++)
{
digit[j]=num%10;
num=num/10;
}
num=num_copy;
for(j=0;j<count_digit_input;j++)
prod=prod*digit[j];
if(prod==input)
printf("%d ",num);
// printf("%d ",count_digit_input);
count_digit_input=0;
}
The solution is simple
public static void findSeed(String str, int number)
{
if(str.equals(Integer.toString(number)))
{
System.out.println(number);
}
else if(str.length() >= Integer.toString(number).length())
{
return;
}
else
{
for(int i=1; i<=9; i++)
{
if(number%i == 0)
{
findSeed(str+Integer.toString(i), number/i);
}
}
}
}
public static ArrayList <Integer> seed(int n) {
HashSet <Integer> factorSet = new HashSet <Integer> ();
ArrayList <Integer> seeds = new ArrayList <Integer> ();
if (n>0) {
factorSet.add(1);
factorSet.add(n);
}
int mid = (int) Math.sqrt(n);
if (mid*mid == n) {
factorSet.add(mid);
}
for (int i=2; i<mid; i++) {
if (n%i == 0) {
factorSet.add(i);
factorSet.add(n/i);
}
}
for (int f : factorSet) {
int factor = f;
int product = f;
while (factor > 0) {
product *= factor%10;
factor /= 10;
}
if (product == n) {
seeds.add(f);
}
}
System.out.println("Number of seeds : "+seeds.size());
return seeds;
}
C++ bruteforce
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
void print(vector<int> results) {
for (int i = 0; i < results.size(); i++) {
cout << results[i] << endl;
}
}
vector<int> findSeeds(int num) {
vector<int> results;
vector<int> values;
int temp;
for (int i = 0; i <= num; i++) {
temp = i;
values.push_back(i);
while (temp != 0) {
if (temp % 10 == 0) {
while (!values.empty()) {
values.pop_back();
}
break;
}
else {
values.push_back(temp % 10);
temp /= 10;
}
}
temp = 1;
while (!values.empty()) {
temp *= values.back();
values.pop_back();
}
if (temp == num) {
results.push_back(i);
}
}
return results;
}
int main() {
int num = 1716;
vector<int> results;
results = findSeeds(num);
print(results);
}
Solved.
Copyrights reserved
int input;
int temp = 1;
int ones, tens, hundreds;
cout << "number : ";
cin >> input;
temp = input;
hundreds = input / 100;
tens = input / 10 - hundreds * 10;
ones = input / 1 - tens * 10 - hundreds * 100;
do {
if (temp % 2 == 0) {
temp = temp / 2;
}
else if (temp % 3 == 0) {
temp = temp / 3;
}
else {
cout << "ERROR\n";
break;
}
hundreds = temp / 100;
tens = temp / 10 - hundreds * 10;
ones = temp / 1 - tens * 10 - hundreds * 100;
if (hundreds < 1) hundreds = 1;
} while (temp*hundreds*tens*ones != input);
cout << "the number is : " << temp << " " << endl;
int input;
int temp = 1;
int ones, tens, hundreds;
cout << "number : ";
cin >> input;
temp = input;
hundreds = input / 100;
tens = input / 10 - hundreds * 10;
ones = input / 1 - tens * 10 - hundreds * 100;
do {
if (temp % 2 == 0) {
temp = temp / 2;
}
else if (temp % 3 == 0) {
temp = temp / 3;
}
else {
cout << "ERROR\n";
break;
}
hundreds = temp / 100;
tens = temp / 10 - hundreds * 10;
ones = temp / 1 - tens * 10 - hundreds * 100;
if (hundreds < 1) hundreds = 1;
} while (temp*hundreds*tens*ones != input);
cout << "the number is : " << temp << " " << endl;
- Oshamajik April 27, 2012#include <iostream> #include <math.h> using namespace std; int main() { int num = 1; cout << "Enter the number: "; cin >> num; int product = 1; int seed = 1; while (seed < (num * 0.5)){ if (num % seed == 0){ int factor = seed; product = factor; while(!(factor == 0)){ int mod = factor % 10; factor = factor / 10; product *= mod; } if (product == num){ cout << "\nThe seed of " << num << " is: " << seed; return 0; } } seed++; } }