Representing number as sum of smaller numbers
the number of ways that integer can be obtained by adding numbers from 0 to
N.
e.g. If the input is 4, output should be 5 (0+4, 1+3, 1+1+2, 1+1+1+1 and
2+2)
-Uday
Member • Oct 29, 2007
Member • Jul 7, 2009
Member • Jul 8, 2009
Sure in Java . Please give some time, I will try it in my free and cool time.pradeep_agrawalI feel this is a good problem statement to code. Any takers?
-Pradeep
Member • Jul 8, 2009
Administrator • Jul 8, 2009
Member • Jul 8, 2009
The_Big_K@Arihant: The first post comes from an experienced programmer 😀 I personally know. It's an exercise for the programming students.
Member • Jul 8, 2009
Easy? Where is your code then man? One more thing, no one is asking for help in this thread ok. Those who like making programs for enhancing their programming skills only, like fun in making any kind of such programs ok. Unfortunately programmers are rarely seen here 😔arihant007Guys dont you think you are doing wrong. You should help people with errors or bugs in programs. Please don't do their homework. They 'll never improve.
This is a very easy program.
I would have helped you, if only you did something and dint know how to go about.
Member • Jul 8, 2009
Member • Jul 10, 2009
Member • Jul 10, 2009
// // Program to calculate the number of ways a number can be the sum // #include "stdafx.h" int iNum, iCombinations,iSplitter; int iFindSum(int iNumber, int iCombo); int _tmain(int argc, _TCHAR* argv[]) { while(1) { printf("Enter the number: "); scanf("%d", &iNum); printf("Possible combinations:\n"); for(iSplitter=1;iSplitter<iNum;iSplitter++) { iFindSum(iNum, iSplitter); } printf("Total Combinations=%d\n",iCombinations); iCombinations=0; } return 0; } int iFindSum(int iNumber, int iBreak) { if(iBreak>iNumber) iBreak-=iNumber; if(iNumber<=iBreak) { printf("%d\n", iNumber); iCombinations++; return iNumber; } else { printf("%d+", iBreak); return(iBreak+iFindSum(iNumber-iBreak,iBreak)); } }
Enter the number: 4 Possible combinations: 1+1+1+1 2+2 3+1 Total Combinations=3 Enter the number: 3 Possible combinations: 1+1+1 2+1 Total Combinations=2Regards,
Member • Jul 10, 2009
Member • Jul 11, 2009
<?php
require_once 'common.php';
$sol = array();
$final_sol = array();
$n = 4;
Factorize($n);
foreach($sol as $str){
$arr = explode('+',$str);
sort($arr);
$final_sol[] = implode('+',$arr);
}
$final_sol = array_unique($final_sol);
$i=0;
foreach($final_sol as $str){
$i++;
echo "$i)$str <br>\n";
}
function Factorize($n){
global $sol;
if($n == 0){
$sol[] = "0";
return;
}
$sol[] = "0+$n";
if($n == 1){
return;
}
GetNaturalFactors($n);
}
function GetNaturalFactors($n,$prepend=""){
global $sol;
if($n == 1){
$sol[] = $prepend."1";
return;
}
if($n == 2 ){
$sol[] = $prepend."1+1";
return;
}
for($i = 1; $i <= $n/2 ; $i++ ){
$sol[] = "$prepend$i+" . ($n-$i);
if($i < $n-$i)
GetNaturalFactors($n-$i,"$prepend$i+");
}
return;
}
?>
Member • Jul 11, 2009
Member • Jul 11, 2009
Possible combinations: 1+1+1+1+1+1 2+2+2 3+3 4+2 5+1 Total Combinations=5Whereas the output should be:
0 + 6 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 + 30 + 6, 1 + 1 + 1 + 1 + 2, 1 + 1 + 1 + 3, 1 + 1 + 2 + 2, 1 + 1 + 4, 1 + 2 + 3 are missing here.
Member • Jul 11, 2009
Member • Jul 11, 2009
sahithi pallavi, let us know what you have already tried and the point where you are stuck. Also post your code.sahithi pallaviHi everyone...I tried this program in C...but I am not successfull. can anybody pls help me....
Member • Jul 12, 2009
Member • Jul 13, 2009
/* * To change this template, choose Tools | Templates * and open the template in the editor. */ package myjava; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashSet; import java.util.Set; /** * * @author shalinig */ public class PossibleAdditionCombinationsProgram { public static Set<String> additionCombinationsSet= new HashSet<String>(); public static void main(String[] args) throws IOException{ BufferedReader br =new BufferedReader(new InputStreamReader(System.in)); System.out.println("Enter any number:"); int number=Integer.parseInt(br.readLine()); System.out.println("0+"+number); additionCombinationsSet.add("0+"+number); for(int i=1;i<=number;i++){ String str=Integer.toString(i); for(int j=1;j<(number/i);j++){ str=str+"+"+Integer.toString(i); } /* Odd number check */ if(number%i!=0){ str=str+"+"+Integer.toString(number%i); } if(str.contains("+") && !additionCombinationsSet.contains(new StringBuilder(str).reverse().toString())){ additionCombinationsSet.add(str); getMoreCombinations(str); } } System.out.println("Possible combinations are:"+additionCombinationsSet.size()); } private static void getMoreCombinations(String str){ System.out.println(str); getMoreReducedFormCombinations(str.split("\\+")); } public static void getMoreReducedFormCombinations(String []s) { String str=""; int length=s.length; int newSecondLastDigit=0; int newLastDigit=0; if(length >2 && (Integer.parseInt(s[length-1])-Integer.parseInt(s[length-2])<=1)){ str=s[0]; for (int i = 1 ; i < s.length-2 ; i++) { str=str+"+"+s[i]; } newLastDigit=Integer.parseInt(s[length-1])+Integer.parseInt(s[length-2]); str=str+"+"+newLastDigit; additionCombinationsSet.add(str); getMoreCombinations(str); } else if(length >2 && (Integer.parseInt(s[length-1])-Integer.parseInt(s[length-2])>1)){ str=s[0]; for (int i = 1 ; i < s.length-2 ; i++) { str=str+"+"+s[i]; } newSecondLastDigit=Integer.parseInt(s[length-2])+1; str=str+"+"+newSecondLastDigit; newLastDigit=Integer.parseInt(s[length-1])-1; str=str+"+"+newLastDigit; additionCombinationsSet.add(str); getMoreCombinations(str); } } }If anyone can understand the above program, Please check where I am going wrong that it is missing few combinations for certain numbers. I am also checking if got it, will correct it.
Member • Jul 13, 2009
0+8 1+1+1+1+1+1+1+1 1+1+1+1+1+1+2 1+1+1+1+1+3 1+1+1+1+2+2 1+1+1+1+4 1+1+1+2+3 1+1+1+5 1+1+2+2+2 1+1+2+4 1+1+3+3 1+1+6 1+2+2+3 1+2+5 1+3+4 1+7 2+2+2+2 2+2+4 2+3+3 2+6 3+5 4+4Whereas, your code give output 20 entries as:
0+8 1+1+1+1+1+1+1+1 1+1+1+1+1+1+2 1+1+1+1+1+3 1+1+1+1+2+2 1+1+1+1+4 1+1+1+2+3 1+1+1+5 1+1+2+4 1+1+3+3 1+1+6 1+2+5 1+3+4 1+7 2+2+2+2 2+2+4 2+3+3 2+6 4+4 5+3The entries missing here are "1+1+2+2+2" and "1+2+2+3".
Member • Jul 14, 2009
Member • Jul 14, 2009
I know many forums that say like same as you you might be knowing this but i know what you say is correctarihant007Guys dont you think you are doing wrong. You should help people with errors or bugs in programs. Please don't do their homework. They 'll never improve.
This is a very easy program.
I would have helped you, if only you did something and dint know how to go about.
Member • Jul 14, 2009
Member • Jul 14, 2009
You can post solution in any language of your choice.safwanIs VB alllowed ?
Member • Jul 15, 2009
#include <iostream> #include <string> using namespace std; int nfact1, nfact2; char factor1[512][512], factor2[512][512]; int main() { int factorize(int, int, char*); int N, n1, n2, n; char a1[512], a2[512], a3[512]; cout << "Please enter the number to be factorized:\t"; cin >> N; // if (N == 1) { cout << "1.\t0 + 1\n"; cout << "Number of factors:\t1\n"; } else if (N == 2) { cout << "1.\t0 + 2\n"; cout << "2.\t1 + 1\n"; cout << "Number of factors:\t2\n"; } else { nfact1 = 1; char a[] = "1 + "; n1 = 1; sprintf(a1,"%d",n1); strcpy(a2,a); strcat(a2,a1); strcpy(factor1[0],a2); for(int i=3; i<=N; i++) { char a[] = "1 + "; n1 = i - 1; sprintf(a1,"%d",n1); strcpy(a2,a); strcat(a2,a1); nfact2 = 1; strcpy(factor2[0],a2); // for (int j=0; j<nfact1; j++) { nfact2++; strcpy(a2,a); strcat(a2,factor1[j]); strcpy(factor2[nfact2-1],a2); } // if (i%2 == 0) n = i/2; if (i%2 != 0) n = (i-1)/2; // int j = 2; while (j <= n) { n1 = i - j; sprintf(a,"%d",j); strcat(a," + "); sprintf(a2,"%d",n1); strcpy(a3,a); strcat(a3,a2); nfact2++; strcpy(factor2[nfact2-1],a3); if (n1%2 == 0) n2 = n1/2; if (n1%2 != 0) n2 = (n1-1)/2; if (n2 >= j) factorize(n1,j,a); j = j + 1; } nfact1 = nfact2; // cout << "Factors of " << i << endl; for (int j=0; j<nfact2; j++) { strcpy(factor1[j],factor2[j]); // cout << j+1 << ".\t" << factor1[j] << endl; } } } cout << "Factors of " << N << endl; cout << "1.\t" << "0 + " << N <<endl; for (int j=0; j<nfact1; j++) { cout << j+2 << ".\t" << factor1[j] << endl; } cout << "Total combinations: " << nfact1+1 << endl; /* Scaffolding code for testing purposes */ cin.ignore(256, '\n'); cout << "Press ENTER to continue..." << endl; cin.get(); /* End Scaffolding */ } // int factorize(int N, int n, char*a1) { int n2, n1, N1; char a2[512],a[512],a3[512],a4[512]; strcpy(a,"\0"); if (N%2 == 0) n1 = N/2; if (N%2 != 0) n1 = (N-1)/2; int j = n; N1 = N; while (j <= n1) { n2 = N1 - j; sprintf(a4,"%d",j); strcat(a,a4); strcat(a," + "); strcpy(a4,a); strcat(a4,a1); sprintf(a2,"%d",n2); strcpy(a3,a4); strcat(a3,a2); nfact2++; strcpy(factor2[nfact2-1],a3); if ((n2-j) >= n) N1 = n2; if ((n2-j) < n) { j = j+1; if (j > n1) break; if (j <= n1) { N1 = N; strcpy(a,"\0"); } } } }Output for 8:-
Please enter the number to be factorized: 8Code will be limited for numbers upto 22, else might have to increase size of arrays.
Factors of 8
1. 0 + 8
2. 1 + 7
3. 1 + 1 + 6
4. 1 + 1 + 1 + 5
5. 1 + 1 + 1 + 1 + 4
6. 1 + 1 + 1 + 1 + 1 + 3
7. 1 + 1 + 1 + 1 + 1 + 1 + 2
8. 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
9. 1 + 1 + 1 + 1 + 2 + 2
10. 1 + 1 + 1 + 2 + 3
11. 1 + 1 + 2 + 4
12. 1 + 1 + 2 + 2 + 2
13. 1 + 1 + 3 + 3
14. 1 + 2 + 5
15. 1 + 2 + 2 + 3
16. 1 + 3 + 4
17. 2 + 6
18. 2 + 2 + 4
19. 2 + 2 + 2 + 2
20. 3 + 2 + 3
21. 3 + 5
22. 4 + 4
Total combinations: 22
Member • Jul 19, 2009
char a[] = "1 + "; n1 = 1; sprintf(a1,"%d",n1); strcpy(a2,a); strcat(a2,a1); strcpy(factor1[0],a2);can be modified to
strcpy(factor1[0],"1 + 1");
char a[] = "1 + "; n1 = i - 1; sprintf(a1,"%d",n1); strcpy(a2,a); strcat(a2,a1); strcpy(factor2[0],a2);can be modified to
n1 = i - 1; sprintf(factor2[0],"1 + %d",n1);
sprintf(a,"%d",j); strcat(a," + "); sprintf(a2,"%d",n1); strcpy(a3,a); strcat(a3,a2); strcpy(factor2[nfact2-1],a3);can be modified to
sprintf(factor2[nfact2-1],"%d + %d",j, n1);-Pradeep
Member • Jul 19, 2009
#include "stdio.h" void displayseries(int* series, int count) { int i = 0; if(count != 0) { for(i = 0; i <= count; i++) { if(i == count) { printf("%d\n", series[i]); } else { printf("%d + ", series[i]); } } } } int find_sum_series(int num, int* series, int count, int sum) { int starting_number = 0; int combination_count = 0; if(count < 0) { starting_number = 1; } else { starting_number = series[count]; } while((sum + starting_number) <= num) { if((sum + starting_number) < num) { count++; series[count] = starting_number; sum += starting_number; combination_count += find_sum_series(num, series, count, sum); count--; sum -= starting_number; } else if((sum + starting_number) == num) { count++; series[count] = starting_number; displayseries(series, count); combination_count++; count--; } starting_number++; } return combination_count; } int main() { int *series = NULL; int count = 0; int num = 0; scanf("%d", &num); if(num < 1) { printf("Invalid number\n"); return 0; } printf("Combinations:\n", num); printf("0 + %d\n", num); series = (int*)malloc(sizeof(int) * num); count = find_sum_series(num, series, -1, 0); printf("Total combinations: %d\n", count); free(series); return 0; }Compile the file with above code and run as:
Member • Jul 19, 2009
Member • Jul 20, 2009