Yahoo Interview Question
Software Engineer / DevelopersExample 9:
Here V - Valid,
DD - Digit duplicate
R - Repeat in other order
1,8 (V) --> 1,2,6 (V) -->1,2,1,5 (DD)
1,2,2,4 (DD)
1,3,5 (V) -->1,3,1,4 (DD)
1,3,2,3 (DD)
2,7 (V) --> 2,1,6 (R)
2,2,5 (DD)
2,3,4 (V)
3,6 (V) --> 3,1,5 (R)
3,2,4 (R)
4,5 (V) --> 4,1,4 (DD)
4,2,4 (R)
4,3,2 (R)
O/p: Only valid out put (Excluding DD and R)
1,8
2,7
3,6
4,5
1,2,6
1,3,5
2,3,4
this is Dynamic Programming question coin minimum denomination
How many ways you can get the denomination for given amount
int n = 10;
func_count(n, n);
int func_count( int n, int m )
{
if ( n == 0 )
return 1;
if ( n < 0 )
return 0;
if ( m <= 0 && n >= 1 )
return 0;
return (func_count(n, m - 1) + func_count(n - m, m));
}
@Anonymous: good point. the algorithm is limited by datatype size i.e. for n >=38, you would already exceed 'double' datatype limit. because 38 can be represented as a sum of 38 1's, we need some other algo for just printing the integers as a sum rather than storing them. i.e. if for n=100 if we can print 100 1's rather than trying to build a datatype that stores 100 1's
A possible logic is can be as follows:=
number if ways we can print sum of n is :-
1 + all possible ways we can print n-1
2 + all possible ways we can print n-2 and so on...
drawback:= repeated series like in case of 5 both 1+1+3 and 3+1+1 will be printed.. can be avoided by keeping hash
Here is a pseudo code for the same
printAllSum(a,n){
if(n==0)
print a;
for(int i=1;i<=n;i++){
add(a,i);
printAllSum(a,n-i);
remove(a,i);
}
}
I believe no polynomial time exists for this problem, as it can be converted to some NP-complete problem.
However, if it asks for "number of ways" you can make n from positive integers in the range 1 to n, polynomial time algorithm is doable (like one pointed before) with complexity O(n^2).
#define MAX_POINT 3
#define ARR_SIZE 100
#include<stdio.h>
/* Utility function to print array arr[] */
void printArray(int arr[], int arr_size);
/* The function prints all combinations of numbers 1, 2, ...MAX_POINT
that sum up to n.
i is used in recursion keep track of index in arr[] where next
element is to be added. Initital value of i must be passed as 0 */
void printCompositions(int n, int i)
{
/* array must be static as we want to keep track
of values stored in arr[] using current calls of
printCompositions() in function call stack*/
static int arr[ARR_SIZE];
if (n == 0)
{
printArray(arr, i);
}
else if(n > 0)
{
int k;
for (k = 1; k <= MAX_POINT; k++)
{
arr[i]= k;
printCompositions(n-k, i+1);
}
}
}
/* UTILITY FUNCTIONS */
/* Utility function to print array arr[] */
void printArray(int arr[], int arr_size)
{
int i;
for (i = 0; i < arr_size; i++)
printf("%d ", arr[i]);
printf("\n");
}
/* Driver function to test above functions */
int main()
{
int n = 5;
printf("Differnt compositions formed by 1, 2 and 3 of %d are\n", n);
printCompositions(n, 0);
getchar();
return 0;
}
import java.util.Vector;
public class SumOfPossibleV2 {
public static Vector<Integer> temp = new Vector<Integer>();
public static void breakDown(int n) {
for (int i = 1; i <= n / 2; i++) {
breakDown(i, n - i);
}
}
public static void breakDown(int min, int val) {
if (val >= min) {
Add(min);
Add(val);
Print();
if ((val - min) >= min) {
RemoveLast();
for (int i = min; i <= val / 2; i++) {
breakDown(i, val - i);
}
RemoveLast();
} else {
RemoveLast();
RemoveLast();
}
}
}
private static final String f = "%d ";
private static void Print() {
Return();
for(int i = 0; i < temp.size();i++){
Joint(temp.get(i));
}
}
private static void Joint(int val){
System.out.print(String.format(f, val));
}
private static void Return(){
System.out.println();
}
private static void Add(int item) {
temp.add(item);
}
private static void RemoveLast() {
temp.remove(temp.size() - 1);
}
}
static public void printPossibilities(int cur, int max) {
for(int i = cur; i > 0; i--) {
int meta = (cur - i);
System.out.print(meta + " + " + i + ", ");
if(meta > 1) {
String ret = "";
while(meta > 1) {
meta--;
for(int j = cur - i; j > meta; j--) {
ret += "1 + ";
}
ret += meta + " + " + i + ", ";
}
System.out.print(ret);
}
System.out.println();
}
}
#include <iostream>
using namespace std;
static void print(int s[], int n);
static void partitionOfSize(int num, int size, int s[], int currentSize);
void generatePartitions(int num)
{
int *s;
s = new int[num];
for(int i = 2; i <= num; i++)
partitionOfSize(num, i, s, i);
}
void partitionOfSize(int num, int size, int s[], int currentSize)
{
int maxElement;
if(currentSize == 1)
{
s[size - currentSize] = num;
print(s, size);
return;
}
maxElement = num/currentSize;
for(int i = 1; i <= maxElement; i++)
{
if(size > currentSize && s[size - currentSize - 1] > i)
continue;
s[size - currentSize] = i;
partitionOfSize(num-i, size, s, currentSize-1);
}
}
void print(int s[], int n)
{
for(int i = 0; i < n; i++)
cout << s[i] << " ";
cout << "\n";
}
<pre lang="" line="1" title="CodeMonkey14744" class="run-this">#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int s,a,d,sum,i;
cout<<"enter the number\n";
cin>>s;
cout<<"\n";
for(d=1;d<=(s-2);d++)
{
for(a=1;a<=(s-1);a++)
{
sum=0;
i=a;
while(sum<s)
{
sum=sum+i;
i=i+d;
}
if(sum==s)
{
i=a;
sum=0;
while(sum<s)
{
sum=sum+i;
cout<<" "<<i;
i=i+d;
}
cout<<"\n";
}
}
}
getch();
}</pre><pre title="CodeMonkey14744" input="yes">
</pre>
Can be easily solved using recursion.
for sum(30)
print(1,29);
sum(30) = sum(29) + {1}<-My Stack
print(1,1,28);
sum(29) = sum(28) + {1,1}
N is the number given.
int stack[N];
sum(int n, int index)
{
if(n==0)
{
print stack;//use a while loop till index -1
return;
}
else
{
for all i=1 to ceil((float)n/2))
{
stack[index] = i;
print stack and n-i; // all elements of stack and n-i
sum(n-i, index+1);
}
}
}
initially call sum(N,0)
1) a number can be represented with sum of 2 digits,3 digits, 4 digit ... maximum digits can be number its self.. where number will be 1+1+1+1+.............1(n times)
2) value of each digit can go max to num/ no of digits... after this cases will get repeated
The approached I use is kind of DP
int path[],int len,int num
// get all the possible combination of digits
for(int digits=2;digits<=num;digits++)
{
evaluate(path,len,num,digits)
}
// function to find all possible solution for a given number of digits in representing sum
void evaluate (int path[], int len , int num, int digit)
{
if(digit==0||num==0)
{
print path[0 to len]
if(num!=0)
print num
return
}
for(int i=0; i<=num/digit;i++)
{
path[len]=i;
evaluate(path,len+1,num-i,digit-1);
}
}
public static void printNum(int n){
int [] array=new int [n];
sum_num(n,0,array,0,0);
}
private static void sum_num(int n,int cur,int [] array, int count,int next){
if (n==cur){
for (int i=0;i<count;i++){
System.out.print(array[i]+",");
}
System.out.println();
}else if (cur>n){
return;
}else{
for (int i=1;i<n;++i){
if (i<next){
continue;
}
cur+=i;
array[count]=i;
sum_num(n,cur,array,count+1,i);{
cur-=i;
}
}
}
}
//Given an integer n , you have to print all the ways in which n can be represented as sum of positive integers.
#include<stdio.h>
//#include<conio.h>
void printall(int n,char str[],int index)
{
if(n==0)
{
printf("%s\n",str);
return;
}
if(n<0)
return;
int i;
for(i =1;i<=n;i++)
{
str[index-1] = i+48;
str[index] = '\0';
index = index+1;
printall(n-i,str,index);
index--;
}
}
int main()
{
int n;
printf("enter a number n\n");
scanf("%d",&n);
// fflush(stdin);
char str[200];
printall(n,str,1);
// getchar();
}
A recursive approach:
void print(int* res,int depth)
{
int i;
for(printf("\n"),i=0;i<depth;printf("%d ",res[i]),++i);
}
void foo(int sum,int N,int* res,int depth)
{
int i;
if(sum<0) return;
if(!sum)
print(res,depth);
else
for(i=1;i<N;i++)
if(!depth || i>=res[depth-1])
{
res[depth]=i;
foo(sum-i,N,res,depth+1);
}
}
Complete code here: ideone.com/z2rcm
#include<stdio.h>
#include<conio.h>
void printall(int n,char str[],int index)
{
if(n==0)
{
printf("%s\n",str);
return;
}
if(n<0)
return;
for(int i =1;i<=n;i++)
{
str[index-1] = i+48;
str[index]='\0';
index = index+1;
printall(n-i,str,index);
index--;
}
}
int main()
{
int n;
printf("enter a number n\n");
scanf("%d",&n);
fflush(stdin);
char str[100];
printall(n,str,1);
getchar();
return 0;
}
public class PrintSum {
public static void main(String[] args) {
printSum (5, "");
}
private static void printSum(int n, String prefix) {
if(n <= 0) {
System.out.println(prefix);
return;
}
for(int i = 1; i <= n; i++) {
String temp = "";
if(prefix.length() == 0)
temp = i + "";
else
temp = "," + i;
printSum(n-i, prefix + temp);
}
}
}
I need to solve this by DP. Just wanna check opinion before I proceed further.
import java.util.*;
import java.lang.*;
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
int input=5;
System.out.println(getRep(input));
}
public static ArrayList<ArrayList<Integer>> getRep(int input)
{
ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
for (int i=1; i<input; ++i)
{
ArrayList<ArrayList<Integer>> templist=get2Rep(input-i);
for (ArrayList<Integer> AL: templist)
{
for (int j=0; j<i; ++j)
AL.add(1);
}
result.addAll(templist);
}
return result;
}
public static ArrayList<ArrayList<Integer>> get2Rep(int input)
{
ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
for (int i=1; i<input; ++i)
{
ArrayList<Integer> templist=new ArrayList<Integer>();
templist.add(i);
templist.add(input-i);
result.add(templist);
}
return result;
}
}
This probably should work.
void partition(int n, int m = 0)
{
int i;
// if the partition is done
if(n == 0){
// Output the result
for(i = 0; i < m; ++i)
printf("%d ", list[i]);
printf("\n");
return;
}
// Do the split from large to small int
for(i = n; i > 0; --i){
// if the number not partitioned or
// willbe partitioned no larger than
// previous partition number
if(m == 0 || i <= list[m - 1]){
// store the partition int
list[m] = i;
// partition the rest
partition(n - i, m + 1);
}
}
}
This one is much easier to understand
void partition(int n, int m = 0)
{
int i;
// if the partition is done
if(n == 0){
// Output the result
for(i = 0; i < m; ++i)
printf("%d ", list[i]);
printf("\n");
return;
}
// Do the split from large to small int
for(i = n; i > 0; --i){
// if the number not partitioned or
// willbe partitioned no larger than
// previous partition number
if(m == 0 || i <= list[m - 1]){
// store the partition int
list[m] = i;
// partition the rest
partition(n - i, m + 1);
}
}
}
This one is much easier to understand
This is the simplest recursion algorithm I can find,
I checked, and it works. Please tell me if you have any questions.
void partition(int n, int m = 0)
{
int i;
// if the partition is done
if(n == 0){
// Output the result
for(i = 0; i < m; ++i)
printf("%d ", list[i]);
printf("\n");
return;
}
// Do the split from large to small int
for(i = n; i > 0; --i){
// if the number not partitioned or
// willbe partitioned no larger than
// previous partition number
if(m == 0 || i <= list[m - 1]){
// store the partition int
list[m] = i;
// partition the rest
partition(n - i, m + 1);
}
}
}
void find(int n,int arr[],int idx)
{
if(n==0)
{
print(arr,idx);
return;
}
int k=idx>0?arr[idx-1]:1;
for(int i=k;i<=n;i++)
{
arr[idx]=i;
if(n-i >=0){
called++;
find(n-i,arr,idx+1);}
}
}
I still don't know thw complexity of this one...someone tell me!!!!
int find_parts(int n)
{
for(int i=1; i<=n-2; i++){
for(int j=i+1; j<=n-1; j++){
for(int k=j+1; k<=n; k++)
{
if((i+j+k) == n)
printf ("*** %d+%d+%d=%d\n", i, j, k, n);
}
}
}
return 0;
}
Time complexity using this approach is O(n^3).
Do you think it will work when sum of 4 or more nos equals 'n'?
E.g. If n is 30, will this print 26,1,1,1,1 or 5,5,5,5,10?
#include <stdio.h>
- ch.v.suresh February 15, 2011#define Max_Size 20
void sum_of_numbers_till_n(int a[],int index_till);
int main()
{
int n = 0,index_till=0;
int a[Max_Size];
while(1)
{
printf("Enter 'n' value : ");
scanf("%d",&n);
if(n==0) break;
a[0] = n;
sum_of_numbers_till_n(a,index_till);
printf("\n\n");
}
}
void sum_of_numbers_till_n(int a[],int index_till)
{
int i,j;
int start_v,end_v;
int b[Max_Size];
for(i=1;i<=(a[index_till]/2);i++)
{
start_v = i;
end_v = a[index_till]-i;
if(start_v == end_v)
return;
for(j=0;j<=index_till;j++)
{
if(start_v==a[j] || end_v==a[j])
{
return;
}
}
for(j=0;j<=(index_till-1);j++)
{
b[j] = a[j];
}
b[index_till] = start_v;
b[index_till+1] = end_v;
printf("\n");
for(j=0;j<=(index_till+1);j++)
printf("%d ",b[j]);
sum_of_numbers_till_n(b,index_till+1);
}
}