Amazon Interview Question SDE-2s
Country: United States
Interview Type: Phone Interview
I think your solution works but it is recursive. If you look at it you are again and again calculating ways to print sub-numbers. A better way would be DP. Create a table to store all ways to create all numbers less than this number and use that table. Fill table from bottom to up.
Easy but tricky question. The key is:
1) save numbers in buffer and print at the end
2) avoid repeat combinations.
void PrintCombo(int num, int* arr, int index )
{
if (num == 0)
{
for (int i = 0; i<index; i++)
{
if (i != 0)
cout << ',';
cout << arr[i];
}
cout << '\n';
return;
}
for (int i = num; i > 0; i--)
{
if (index == 0 || i <= arr[index - 1])
arr[index] = i;
else
continue;
PrintCombo(num - i, arr, index + 1);
}
}
int main()
{
int num;
cout << "Enter the number \n";
cin>>num;
int *arr = new int[num];
PrintCombo(num, arr, 0);
}
if index is 0 it cannot have any other to compare with. So OR is correct relationship. If we use and it will try to obtain an array element with -1 as index which is wrong
Great answer Brandy
Two solutions in Python. The first one uses a global list to keep the numbers that sum to the given number. The second one, a bit more complicated, just keeps the list in the function, and returns it:
globalseq = []
def sumnumberglobal(numb, seq = []):
if numb == 0:
globalseq.append(seq)
if numb > 0:
i = 1
while numb-i >= 0:
seqb = seq + [i]
sumnumber(numb-i, seqb)
i+=1
def sumnumber(numb, seq = []):
if numb == 0:
return [seq]
if numb > 0:
results = []
i = 1
while numb-i>=0:
seqb = seq + [i]
results+=sumnumber(numb-i, seqb)
i+=1
return results
sumnumber(5)
print globalseq
print sumnumber(5)
static void PrintSumCombination(int[] array, int start,int sum, int targetSum, List<int> numbersSoFar)
{
if(targetSum == sum)
{
foreach(int index in numbersSoFar)
{
Console.Write("{0}{1}",index.ToString(), " ");
}
Console.WriteLine();
}
else
{
for (int index = start; index < array.Length; index++)
{
sum += array[index];
if (sum <= targetSum)
{
numbersSoFar.Add(array[index]);
PrintSumCombination(array, index, sum, targetSum, numbersSoFar);
numbersSoFar.RemoveAt(numbersSoFar.Count - 1);
sum -= array[index];
}
else
return;
}
}
}
static void Main(string[] args)
{
int[] arr = { 1, 2, 3, 4, 5, 6 };
List<int> list = new List<int>();
PrintSumCombination(arr,0, 0, 6, list);
}
O/P:
1 1 1 1 1 1
1 1 1 1 2
1 1 1 3
1 1 2 2
1 1 4
1 2 3
1 5
2 2 2
2 4
3 3
6
private static ArrayList<ArrayList<Integer>> print(int number) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (number <= 0) return result;
dfs(1, number, 0, result, new ArrayList<Integer>());
return result;
}
private static void dfs(int index, int number, int current, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> sub) {
if (current == number) {
ArrayList<Integer> tmp = new ArrayList<Integer>();
tmp.addAll(sub);
result.add(tmp);
return;
}
for (int i = index; i <= number; i++) {
current += i;
if (current <= number) {
sub.add(i);
dfs(i, number, current, result, sub);
sub.remove(sub.size() - 1);
current -= i;
} else {
return;
}
}
}
void PrintAllWays(std::vector<int> previous,
int value)
{
if (value < 0)
{
return;
}
else if (value == 0)
{
std::cout<<"\r\n";
std::vector<int>::iterator it = previous.begin();
while (it != previous.end())
{
std::cout<<" "<<*it;
++it;
}
}
else
{
for (int i = 1; i <= value; i++)
{
std::vector<int> with = std::vector<int>(previous.begin(), previous.end());
with.push_back(i);
PrintAllWays(with, (value - i));
with.pop_back();
}
}
}
public class Problem {
final int NUM_GENERATE = 50;
public void genNum(String pattern, int sum) {
if (sum > NUM_GENERATE || pattern.length() > NUM_GENERATE * 4) {
return;
} else if (sum == NUM_GENERATE) {
System.out.println(pattern);
}
for (int i = 1; i <= NUM_GENERATE; i++) {
if (pattern.length() > 0) {
int lastNum = Integer.parseInt(pattern.substring(pattern.lastIndexOf(',') + 1, pattern.length()));
if (i >= lastNum) {
genNum(pattern + "," + i, sum + i);
}
} else {
genNum(pattern + "," + i, sum + i);
}
}
}
public static void main(String args[]) {
Problem p1 = new Problem();
p1.genNum("", 0);
}
}
#include<iostream>
using namespace std;
void DoArrangement(int arr[], int i, int n,int k, int sum, int last)
{
if(sum > k) return;//stop unwanted case
if(sum == k)
{
for(int x = 0; x <i;x++)
cout<<arr[x]<<" + ";
cout<<endl;
return;
}
else if(i == n)
{
return;
}
else
{
if(last <= 1)
{
arr[i] = 1;
DoArrangement(arr,i+1,n,k,sum+1,1);
}
if(last <= 2)
{
arr[i] = 2;
DoArrangement(arr,i+1,n,k,sum+2,2);
}
if(last <= 3)
{
arr[i] = 3;
DoArrangement(arr,i+1,n,k,sum+3,3);
}
if(last <= 4)
{
arr[i] = 4;
DoArrangement(arr,i+1,n,k,sum+4,4);
}
if(last <= 5)
{
arr[i] = 5;
DoArrangement(arr,i+1,n,k,sum+5,5);
}
}
}
int main()
{
int arr[] = {0,0,0,0,0};
DoArrangement(arr,0,5,5,0,1);
}
Output:-
1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 2
1 + 1 + 3
1 + 2 + 2
1 + 4
2 + 3
5
Here is C# Code
public static void FindAdditionCombinations(int number)
{
RecursivePrintWays("1", number);
Console.WriteLine(number);
}
public static void RecursivePrintWays(string s, int number)
{
if (number == 2)
{
if (s.IndexOf('2') == -1)
{
s += " 1";
Console.WriteLine(s);
}
return;
}
for (int i = 1; i <= number/2; i++)
{
RecursivePrintWays(s + " " + i, number - i);
}
Console.WriteLine(s + " " + (number - 1));
}
public static void main( String[] args ) {
printAddtionString( 10, "", 0 );
}
public static void printAddtionString( int Number, String s, int baseNum ){
if( s.equals("") )
System.out.println( Number );
else
System.out.println( s+","+Number );
int i = 1;
if( baseNum > 1 ) i = baseNum;
for( ; i <= Number/2;i++ ) {
String tmp = "";
if( s.equals("") )
tmp = i+"";
else
tmp = s+","+i;
printAddtionString( Number - i, tmp, i );
}
}
public string printSeq(int num)
{
string result = num.ToString() + "\n";
for (int i = 1; i <= num; i++)
{
if (i <= num / 2)
result += (num - i) + "," + i + "\n";
if (i > 1 && num-i > 0)
{
for (int k = 0; k < i; k++)
result += "1,";
result += (num - i) + "\n";
}
}
return result;
}
Result:
5
4,1
3,2
1,1,3
1,1,1,2
1,1,1,1,1
#include "stdafx.h"
#include <vector>
using std::vector;
void PrintNumHelper(int num, int start, vector<int> &vec){
if (num == 0){
for (int i = 0; i < vec.size(); i++){
printf("%d, ", vec[i]);
}
printf("\n");
}
for (int j = start; j <= num; j++){
vec.push_back(j);
PrintNumHelper(num - j, j, vec);
vec.pop_back();
}
return;
}
void PrintNum(int i){
vector<int> vec;
if (i == 0){
printf("%d\n", i);
}
PrintNumHelper(i, 1, vec);
return;
}
int _tmain(int argc, _TCHAR* argv[])
{
PrintNum(5);
return 0;
}
public static void main(String[] args) {
int x = 5;
int rem = x%2==0?x/2:(x/2+1);
for (int i = 1; i < x; i++) {
String s = "";
for (int j = 1; j <= rem; j++) {
int count = i ;
s = i+"";
while(true)
{
count = count + j;
s= s+"," +j;
if(count == x)
{
System.out.println(s);
break;
}
if(count > x)
{
break;
}
}
}
}
}
The below code is working fine..
public static void main(String[] args) {
int x = 5;
int rem = x%2==0?x/2:(x/2+1);
for (int i = 1; i < x; i++) {
String s = "";
for (int j = 1; j <= rem; j++) {
int count = i ;
s = i+"";
while(true)
{
count = count + j;
s= s+"," +j;
if(count == x)
{
System.out.println(s);
break;
}
if(count > x)
{
break;
}
}
}
}
}
var strings = new List<string>();
for (int i = 1; i <= 10; i++)
{
string prefix = i == 1 ? string.Empty : ("1,");
PrintNumber(i, prefix, strings);
}
strings.ForEach(x => Console.WriteLine(x + " = " + x.Split(",".ToCharArray()).Sum(y => int.Parse(y))));
private static void PrintNumber(int x, string prefix, List<string> results)
{
if (x == 1)
{
results.Add("1");
}
else
{
List<string> temp = new List<string>();
foreach (string t in results)
{
temp.Add(prefix + t);
}
results.Clear();
results.AddRange(temp);
results.Add(x.ToString());
int index = 2;
while (index <= x / 2)
{
results.Add(index.ToString() + "," + (x - index).ToString());
index++;
}
}
}
Just the quick and dirty recursive version here:
public void subDivide(int num, int min, String prefix) {
for (int i = 1; i <= num/2 && i >= min; i++) {
// We need to iterate only till Math.floor(num/2) and division in java by default rounds to the lower value, so not using the function here.
if("".equals(prefix)){
System.out.println(""+(num - i)+"+"+i);
prefix += i;
}
else{
System.out.println(""+(num - i)+"+"+i+"+"+prefix);
prefix += "+"+i;
}
subDivide(num-i,i, prefix);
}
}
The initial call say, for 5 would be subDivide(5,0,"");
Due to lots of String concatenations this is not efficient, and a Stringbuilder should be used ideally.
Note : This does not print the original input number again, as its just seemed redundant, but that can be done by printing the input number before making the function call.
/* This returns a List O/P can be formatted as needed*/
public List<String> make(Integer n, List<String> L)
{
if (n == 1) {
String s = "1";
L.add(s);
return L;
}
else
{
List<String> L1 = make(n-1, L);
List<String> L2 = addOneToAll(L1);
L2.add(n.toString());
return L2;
}
}
private List<String> addOneToAll(List<String> L)
{
List<String> apendedList = new ArrayList<>();
for (int i = 0; i < L.size(); i++) {
String s = L.get(i);
apendedList.add(s);
}
return apendedList;
}
public static void main(String[] args) {
int x = 5;
get(x);
}
public static void get(int x){
for (int i = 1; i <= x; i++) {
get(x,i,""+i,i);
}
}
public static void get(int x,int sum,String result,int last){
if(sum==x)
System.out.println(result);
else{
for (int i = last; i <= (x-sum); i++) {
get(x,sum+i,result+i,i);
}
}
}
Result:
11111
1112
113
122
14
23
5
package com.test;
public class MakeANumber {
/**
* Write a function, for a given number,
* print out all different ways to make this number,
* by using addition and any number equal to or
* smaller than this number and greater than zero.
* @param args
*/
public static void main(String[] args) {
int num = 6;
int formedNumber = 0;
for(int i = 0; i<num;i++){
formedNumber=i+=i;
if(i==num){
break;
}
}
System.out.println(formedNumber);
}
}
/**
* @param args
*/
public static void main(String[] args) {
List<List<Integer>> list = sumToNum(5);
for(List<Integer> l: list){
for (int i: l){
System.out.print(i + ",");
}
System.out.println("");
}
}
public static List<List<Integer>> sumToNum(int n){
List<List<Integer>> list = new ArrayList<List<Integer>>();
dfs(list, new ArrayList<Integer>(), n);
return list;
}
private static void dfs(List<List<Integer>> list, ArrayList<Integer> l, int n) {
if( n < 0 ){
return;
}
if(n == 0){
list.add(new ArrayList<Integer>(l));
return;
}
for (int i=1; i<=n; i++){
if(l.size() > 0 && l.get(l.size()-1)>i) continue;
l.add(i);
dfs(list, l, n-i);
l.remove(l.size()-1);
}
}
package com.gs.interviewprep.algo;
import java.util.ArrayList;
import java.util.List;
/**
* Created by dhruv on 06/08/14.
*/
public class PrintCombinations
{
public static void main(String[] args)
{
List<List<Integer>> numList = new ArrayList<List<Integer>>();
new PrintCombinations().getCombinations(5 , numList);
}
private void getCombinations(int value , List<List<Integer>> numList)
{
for(int num = 1 ; num < value ; num++)
{
int numRemaining = value - num;
List<Integer> valueList = new ArrayList<Integer>();
valueList.add(num);
valueList.add(numRemaining);
int sizeOfList = numList.size();
if(sizeOfList > 0) {
List<Integer> copyOfOldList = new ArrayList<Integer>(numList.get(sizeOfList - 1));
copyOfOldList.remove(copyOfOldList.size()-1);
copyOfOldList.addAll(valueList);
numList.add(copyOfOldList);
}
else
{
numList.add(valueList);
}
getCombinations(numRemaining , numList);
System.out.println(numList.get(numList.size()-1));
numList.remove(numList.size()-1);
}
}
}
- Suraj Prakash May 25, 2014void printSeq(int num, int a[], int len,int s){ if(num <= 0){ for(int j=0;j<len;j++) cout<<a[j]<<","; cout<<endl; return; } for(int i = s; i <= num; i++){ a[len] = i; printSeq(num-i,a,len+1,i); } } int main(){ int a[5]; printSeq(5,a,0,1); cin.get(); return 0; }