Microsoft Interview Question
Country: United States
This can be done with recursion. The only trick is to make sure that the next element of the sum is not greater than the previous (otherwise it will generate duplicates).
public class OddPrinter {
public static void main(String[] args) {
printOdd(8, Integer.MAX_VALUE, "");
}
public static void printOdd(int n, int prevPrint, String s){
for (int i=1;i<=n;i+=2){
if (prevPrint >= i) {
if (n-i == 0) {
System.out.println(s + Integer.toString(i));
} else
printOdd(n-i, i, s + Integer.toString(i) + "+");
}
}
}
}
sorry for confusion, I mean print all integer partitions of a given number in odd parts (not compositions, i.e. order does not matter).
for example, given n = 8:
we have 8 = 7 + 1, 8 = 5 + 3, etc.
Here is the solution in JAVA
public static void compositions(int num){
for(int i =1;i<num;i +=2){
int rem = num%i;
int divident = num/i;
if(rem%2 !=0)
System.out.print(rem);
if(rem ==0 || rem%2 !=0){
// Print the composition based on divident
for(int j=divident;j>0;j--)
System.out.print("+"+i);
System.out.println("");
if(i>1){
// get the i in 1s
String iIn1s = "";
for(int temp=i;temp>0;temp--)
iIn1s += "+"+1;
for(int j=1;j<divident;j++){
if(rem%2 !=0)
System.out.print(rem);
for(int k=j;k>0;k--)
System.out.print(iIn1s);
for(int l=(divident-j);l>0;l--)
System.out.print("+"+i);
System.out.println("");
}
}
}
}
}
void generateOdd(int n, vector<int> &result)
{
if ( n == 0 )
{//print result
int len = result.size();
for ( int i = 0; i<len-1; i++)
cout<<result[i]<<"+";
cout<<result[len-1]<<endl;
}
int min = n;
if ( result.empty() == false )
min = *(result.end() - 1);
for ( int j = n > min ? min : n; j>0; j--)
{
if ( (j & 0x1) == 0 )
continue;
if ( n - j > -1 )
{
result.push_back(j);
generateOdd(n-j, result);
result.pop_back();
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
vector<int> res;
generateOdd(11, res);
return 0;
}
see above is nothing but a different form of knapsack problem which sum to particular weight.. here total weight is 8 and values are natural numbers.... search google for fractional knapsack problem .. Now the algo is everywhere all you need to do is code in your known language....
Hemanthed
see above is nothing but a different form of knapsack problem which sum to particular weight.. here total weight is 8 and values are natural numbers.... search google for fractional knapsack problem .. Now the algo is everywhere all you need to do is code in your known language....
Hemanthed
see let the sum 8 be maximum weight ....
and our denomination to make such a sum be 1,2,3,4,5,6,7,....... k where k<sum here k is less than 8 so k=7.
now print all the maximum possible sets of find sum 8 from giving denominations...
u can do this problem with dynamic programming also.....
see following link so that you will get an idea ..."ww.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Greedy/greedyIntro."
I am still not sure whether you are referring to fractional knapsack algorithm where a greedy strategy works ?
or to the DP algorithm to find if it's possible to supply a change using coins with certain denominations ?
I think neither of these algorithms apply to this problem because, for example, the DP algorithm just provides you with the answer if it's *feasible* to supply a change but does not give you all possible ways (partitions) to do that
/**print all compositions of a number in odd parts, i.e. for n = 8:
7 + 1
5 + 3
5 + 1 + 1 + 1
3 + 3 + 1 + 1
3 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1**/
#include<stdio.h>
#include<stdlib.h>
int *result;
int num;
void print_result(int *r,int init, int num)
{
int flag=0,i=0,temp;
//if(!r[init])
// return;
printf("\n");
for(i=init;i<num;i++)
{
if(r[i])
{
temp=r[i];
if(!flag)
{
flag=1;
printf("%d",i);
temp--;
while(temp)
{
printf("+%d",i);
temp--;
}
}
else
{
while(temp)
{
printf("+%d",i);
temp--;
}
}
}
}
}
void get_all_odd_sums(int init, int start, int target)
{
if(start>target)
{
return;
}
if(start==target)
{
result[start]++;
print_result(result,init,num);
result[start]--;
return;
}
result[start]++;
// target-=start;
get_all_odd_sums(init, start,target-start);
result[start]--;
if(result[init])
get_all_odd_sums(init, start+2,target);
}
void print_all_odd_comb(int n)
{
int i,j;
result=(int *)malloc(n*sizeof(int));
for(i=0;i<n;i++)
{
result[i]=0;
}
for(i=1;i<(n/2);i+=2)
{
// printf("\ni=%d",i);
get_all_odd_sums(i,i,n);
}
}
int main()
{
//int num;
printf("n=");
scanf("%d",&num);
print_all_odd_comb(num);
return 0;
}
#include<iostream>
using namespace std;
#define N 11
void print_required_numbers(int intermediate[], int i_end, int start)
{
/* This condition is to avoid printing the sets which contains exactly one element as output*/
if( i_end == 1 && start == N)
return;
for(int i=0;i<i_end;i++)
{
cout<<intermediate[i]<<" ";
}
for(int j=start;j<N;j++)
{
cout<<1<<" ";
}
cout<<endl;
for(int k=start+2;k<N;k+=2)
{
/* This condition is to remove the duplicate set */
if( i_end-1 >=0 )
{
if( k-start+1 < intermediate[i_end-1] )
{
continue;
}
}
intermediate[i_end] = k-start+1;
print_required_numbers(intermediate,i_end+1,k+1);
}
}
int main()
{
int intermediate[N] = {0};
print_required_numbers(intermediate,0,0);
getchar();
return 0;
}
For better understanding just remove all if conditions and execute the program and look at output.
Again add all the if conditions and see the difference.
Intermdeiate array stores already added numbers.
private static void Printer(int n,int cur, int []array,int count,int next){
if (cur==n){
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+=2){
if (i<next){
continue;
}
cur+=i;
array[count]=i;
Printer(n,cur,array,count+1,i);
cur-=i;
}
}
}
I used recursion. Use a vector<int> to the partial sum.
void solve(int n, vector<int>&v) {
int k = v.size();
if (n==0) {
ostringstream oss;
rep(i,k-1)
oss << v[i] << '+';
oss << v[k-1];
cout << oss.str() << endl;
return;
}
int curr = (k==0? n : v[k-1]);
curr = min(n,curr);
curr -= !(curr%2);
for (int i = curr; i >0; i-=2) {
v.push_back(i);
solve(n-i,v);
v.resize(k);
}
}
void odd_sum(int n)
vector<int> v;
solve(n,v);
}
print_comb(int n,int sum,int a[],int x)
{
for(int i=1:i<n;i+=2)
{
sum+=i;
a[x++]=i;
if(sum == n)
{
for(int j=0;j<x;j++)
printf("%d ",a[j]);
printf("\n");
} else if (sum > n) {
return;
} else {
print_comb(n,sum,a,x);
}
}
}
Initial call:print_comb(8,0,a[20],0)
This is raw code.Given for checking the logic.If there is any flaw in logic?
PrintOddCombination.print(new int[8], 0, 8, 1);
public static void print(int[] arr, int len, int num, int start)
{
if (num == 0)
{
printArray(arr, len);
return;
}
int i = 0;
for (i = start; i <= num; i = i + 2)
{
arr[len++] = i;
print(arr, len, num - i, i);
len--;
}
}
public static void printArray(int[] arr, int len)
{
for (int i = 0; i < len; i++)
{
System.Console.Write(" " + arr[i]);
}
System.Console.WriteLine();
}
Here is the working java solution based on the partition algorithm described above
public static void main(String[] args) {
int no = 8;
generateSum(8);
}
// populate this array with all the odd numbers till
// the given no like following
static int V[];
static Stack<Integer> s = new Stack<Integer>();
static void generateSum(int no) {
V = new int[no/2+1];
for(int i=0; i<V.length;i++)
V[i] = 1+i*2;
printSumCombination(no, V.length-1);
}
static void printSumCombination(int no, int index) {
if(no==0 && index ==-1) {
for(Object n: s.toArray())
System.out.printf("%d ", n);
System.out.printf("\n");
return;
}
for(int i = index; i>=0;i--) {
if(no==0) {
for(Object n: s.toArray())
System.out.printf("%d ", n);
System.out.printf("\n");
return;
}
int x = no;
int c = 0;
// adding the same integer multiple times and calling for next
// combination
if(x<V[i]) {
printSumCombination(x,i-1);
return;
} else {
while(x>=V[i]) {
x=x-V[i];
s.push(V[i]);
c++;
printSumCombination(x,i-1);
}
// popping out all the occurrences of this integer form the stack as
// all the combination pertaining to this integer is covered
while(c-->0)
s.pop();
}
}
}
Let Ways[i][j] represent no of ways of partitioning i such that using minimum value of j
Ways[i][j] = Ways[i-j][j] + Ways[i][j+2]
So need to find Ways[n][1] .
int CountWays(int N) {
int i, j, k;
int size = N+1;
int W[size][size];
for (i = 0; i < size; ++i) {
for (j = 0; j < size; ++j) {
W[i][j]=0;
}
}
int start;
if(N%2 ==0)
start=N-1;
else
start=N;
for (i = 0; i <size; i++) {
for (j=start; j >=0; j-=2) {
if(i<j)
W[i][j] = 0;
else if(i==j)
W[i][j] = 1;
else
W[i][j] = W[i-j][j] + W[i][j+2];
}
}
return W[N][1];
}
void printComposition( int n ){
if( n == 0){
return;
}
else if( n == 1){
cout << n << " ";
}
else{
if( n % 2 == 0 ){
printComposition( n - 1);
cout << " + ";
printComposition( 1 );
}
else{
printComposition( n - 2 );
cout << " + ";
printComposition( 2 );
}
}
}
int main(){
for(int i = 0; i <= 10; i++){
printComposition( i );
cout << endl;
}
return 0;
}
1 #include <iostream>
2 #include <vector>
3
4 using namespace std;
5
6 void printComp(int arr[], int len, vector<int> &vec, int N) {
7 if(arr==0||len<0||N<0) return;
8
9 if(0 == N) {
10 for(int i = 0; i < vec.size(); i++)
11 cout << vec[i] << " ";
12 cout << endl;
13 return;
14 }
15 for(int i = 0; i < len; i++) {
16 vec.push_back(arr[i]);
17 printComp(arr+i, len-i, vec, N-arr[i]);
18 vec.pop_back();
19 }
20 }
21
22
23 int main() {
24 int N = 8;
25 int arr[N/2];
26 for(int i = 0; i < N/2; i++)
27 arr[N/2-1-i] = 2*i+1;
28
29 for(int i = 0; i < N/2; i++)
30 cout << arr[i] << "->";
31 cout << endl;
32
33 vector<int> vec;
34 printComp(arr, N/2, vec, N);
35
36 return 0;
37 }
1 #include <iostream>
2 #include <vector>
3
4 using namespace std;
5
6 void printComp(int arr[], int len, vector<int> &vec, int N) {
7 if(arr==0||len<0||N<0) return;
8
9 if(0 == N) {
10 for(int i = 0; i < vec.size(); i++)
11 cout << vec[i] << " ";
12 cout << endl;
13 return;
14 }
15 /*
16 for(int i = 0; i < len; i++) {
17 vec.push_back(arr[i]);
18 printComp(arr+i, len-i, vec, N-arr[i]);
19 vec.pop_back();
20 }
21 */
22 vec.push_back(arr[0]);
23 printComp(arr, len, vec, N-arr[0]);
24 vec.pop_back();
25 printComp(arr+1, len-1, vec, N);
26 }
27
28
29 int main() {
30 int N = 8;
31 int arr[N/2];
32 for(int i = 0; i < N/2; i++)
33 arr[N/2-1-i] = 2*i+1;
34
35 for(int i = 0; i < N/2; i++)
36 cout << arr[i] << "->";
37 cout << endl;
38
39 vector<int> vec;
40 printComp(arr, N/2, vec, N);
41
42 return 0;
43 }
#include <iostream>
#include <vector>
using namespace std;
vector<int> odd_parts;
/*
recursive print_odd_parts method
paramaters:
r: remaining part the number, for which we compute odd parts.
d: position of current odd number in the odd number list
m: max odd number we can start with.
m is used to print combination, not the permutation.
example: we print 8=5+3+1, but skip 8=3+5+1.
*/
void print_odd_parts(int r, int d, int m)
{
if(r== 0)
{
cout << odd_parts[0];
for(int j=1; j < odd_parts.size(); j++)
if(odd_parts[j] > 0)
cout << "+" << odd_parts[j];
cout << endl;
return;
}
int largest_odd_number = m % 2 == 0? m-1:m;
for(int i = largest_odd_number; i >=1; i-=2)
{
if(d == 0)
{
for(int j=0; j < odd_parts.size(); j++)
odd_parts[j] = 0;
}
odd_parts[d] = i;
m = r-i<=i?r-i:i; // this generates combination
// m = r-i; this generates permutation.
print_odd_parts(r-i, d+1,m);
}
}
int main()
{
int n = 11;
odd_parts.resize(n);
cout << "odd parts of " << n << endl;
print_odd_parts(n, 0,n);
}
Here is a java code that generate it:
private static void printCombinations(int n, String currResult, int startI) {
if (n == 0)
System.out.println(currResult);
else if (n > 0) {
for (int i = startI; i > 0; i-= 2)
printCombinations(n - i, currResult + i
+ (n - i == 0 ? "" : " + "), i);
}
}
public static void printCombinations(int n) {
int startI = n;
if (startI % 2 == 0)
startI--;
printCombinations(n, "", startI);
}
public static void backtrack(int x,int sum,int in) {
if (sum == x) {
for (int j = 0 ; j < cnt ; j++)
System.out.print(p[j]+" ") ;
System.out.println("") ;
return ;
}
for (int i = in; i >=1; i-=2)
if ( sum+i <= x ) {
sum+=i ;
p[cnt++] =i ;
backtrack(x,sum,i);
sum-=i ;
cnt--;
}
}
backtrack(x,0,x%2==0?(x-1):x);
this is a special case of a more general partition problem that can be formulated as follows. Find all partitions of an integer 'x' with respect to V = {v[0], ..., v[n-1]}
In other words:
x = c[0]*v[0] + ... + c[n-1]*v[n-1] where each c[i] >= 0 and v[i] <= x.
Accordingly, in our case, say for x = 8
we have: V = {1, 3, 5, 7} since we are only interested in odd parts.
The general problem, as I stated it, can be solved using a simple recursive algorithm:
- suppose we are given an integer 'x'
- take v[i], partition recursively the number y = x - c[i]*v[i]
using parts v[0]..v[i-1] for all possible multiples c[i], i.e.
c[i] goes from 1 to floor(x / v[i])
and the output:
- xxx April 17, 20121: 9 + 1 + 1 +
2: 7 + 3 + 1 +
3: 7 + 1 + 1 + 1 + 1 +
4: 5 + 3 + 1 + 1 + 1 +
5: 5 + 3 + 3 +
6: 5 + 1 + 1 + 1 + 1 + 1 + 1 +
7: 5 + 5 + 1 +
8: 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 +
9: 3 + 3 + 1 + 1 + 1 + 1 + 1 +
10: 3 + 3 + 3 + 1 + 1 +
11: 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 +