Coffee Room
Discuss anything here - everything that you wish to discuss with fellow engineers.
12796 Members
Join this group to post and comment.
uday.bidkar • Oct 24, 2007

# Representing number as sum of smaller numbers

Write a C program that will take a positive integer(N) as input and output
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
parag_kulkarni • Oct 30, 2007
Re: Write a C program

Hi All,

I dont have C compiler available. I have written this program in C#.NET.

The program works fine except for the fact that it outputs one repeate combination. I am trying to rectify the logic and will post it once i have perfect answer.

For Example:
If our input number is 5 then program will output as
0 + 5
1 + 4
1 + 1 + 3
1 + 1+ 1 + 2
1 + 1+ 1+ 1 + 1
1 + 1+ 2 + 1 --> This is extra.
1 + 2 + 2
2 + 3

Regards,
Parag Kulkarni

-----------------------------
Author: Parag Kulkarni
-----------------------------
using System;
using System.Collections.Generic;
using System.IO;
class Program
{
static List list = new List();
static void Main(string[] args)
{
int i = 5; // This is our Input number
int j = 0, k = i;
Console.WriteLine(string.Format("{0} + {1} ", j++, k));
while (j < k)
{
k = i - j;
Console.WriteLine(string.Format("{0} + {1} ", j, k));

mod(k, j, j.ToString() + " + {0}");
j++;

foreach (string str in list)
{
Console.WriteLine("{0}", str);
}

list.Clear();

}

}

private static void mod(int i, int j, string formatString)
{

int k, l;
l = j;
if (j > i)
return;
else
{
k = i - j;
while (j <= k)
{
k = i - j;
list.Add(string.Format(formatString, string.Format("{0} + {1} ", j, k)));
mod(k, j, string.Format(formatString, j) + "+ {0}");
j++;

}
}

}
}
Re: Write a C program

I feel this is a good problem statement to code. Any takers?

shalini_goel14 • Jul 8, 2009
Re: Write a C program

I feel this is a good problem statement to code. Any takers?

Sure in Java . Please give some time, I will try it in my free and cool time.

Anyone else ?
arihant007 • Jul 8, 2009
Re: Write a C program

Guys 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.
Kaustubh Katdare • Jul 8, 2009
Re: Write a C program

@Arihant: The first post comes from an experienced programmer 😀 I personally know. It's an exercise for the programming students.
arihant007 • Jul 8, 2009
Re: Write a C program

The_Big_K
@Arihant: The first post comes from an experienced programmer 😀 I personally know. It's an exercise for the programming students.

oH Ok. Thanks for informing,cause I never really appreciate people outsourcing their homeworks. 😉

No oofense for what i said. ;-)
shalini_goel14 • Jul 8, 2009
Re: Write a C program

arihant007
Guys 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.
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 😔
silverscorpion • Jul 8, 2009
Re: Write a C program

Ok, cool. He didnt give the code because, as he said, he thought it was a homework.

May be it is easy.. Who knows. Btw, I'll try to post my code soon. Chill!! 😀😀
prasath_amd • Jul 10, 2009
Re: Write a C program

I'm trying it in both C & Java, i'll post the source & output for both once i'm done.:sshhh:
Re: Write a C program

Hi Folks!

This is my version of the solution. I wanted to write a straight, simple and short recursive program, but it turned out to be longer then expected.
```//
// 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;iSplitteriNumber)
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=2 ```
Regards,

Debu 😀

Edit: Oops, it seems the program was supposed to be from 0 to N. My code runs from 1 to N. Sorry, I can't be fussed enough to fix it.
shalini_goel14 • Jul 10, 2009
Re: Write a C program

Hi debu,

Good attempt man 😀 but I guess for Input =4, there should be 5 combinations. (1+1+2) is missing in your output I guess.[About Program I am not sure. ]
uday.bidkar • Jul 11, 2009
Re: Write a C program

Solution in PHP, (I am loving this language 😀)
``` phprequire_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 \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;}?> ```
uday.bidkar • Jul 11, 2009
Re: Write a C program

The post still remains open for C program
Re: Write a C program

@Uday
Good code buddy, liked the use of available function. Mastering over all languages huh.😉

@All
Will wait for few more days, for other to post their code in any language, before posting my code.

@Debu
When input is 4, the number of output should be 5 (0+4, 1+1+2) are missing here. When input is 6 your code generate output as:

```Possible combinations:
1+1+1+1+1+1
2+2+2
3+3
4+2
5+1
Total Combinations=5
```
Whereas 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 + 3
```
0 + 6, 1 + 1 + 1 + 1 + 2, 1 + 1 + 1 + 3, 1 + 1 + 2 + 2, 1 + 1 + 4, 1 + 2 + 3 are missing here.

The code is not giving all possible results because you are having a for loop which iterates 1 to (N-1), i.e., (N-1) time. And each loop generates a single series which starts from the value of the loop counter and generates sub-sequent numbers with difference of the loop counter (the difference/splitter is set to 1 when the remaining value is less then the loop counter).

The thing missing here is:
- There will always a series 0 + N (in this case 0 + 5).6
- There can be multiple series that start with same value (e.g., 1 + 1 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 2, 1 + 1 + 1 + 3, 1 + 1 + 2 + 2, and 1 + 1 + 4).
- There can be series whose difference of subsequent digits might not be same (e.g., 1 + 1 + 2 + 2 and 1 + 2 + 3).

Re: Write a C program

Hi everyone...I tried this program in C...but I am not successfull. can anybody pls help me....
Re: Write a C program

sahithi pallavi
Hi everyone...I tried this program in C...but I am not successfull. can anybody pls help me....
sahithi pallavi, let us know what you have already tried and the point where you are stuck. Also post your code.

uday.bidkar • Jul 12, 2009
Re: Write a C program

Remove the "require_once 'common.php';" line from PHP code i posted before trying the code at your end
shalini_goel14 • Jul 13, 2009
Re: Write a C program

Below is what I tried

```/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package myjava;

import java.io.IOException;
import java.util.HashSet;
import java.util.Set;

/**
*
* @author shalinig
*/

public static Set additionCombinationsSet= new HashSet();

public static void main(String[] args) throws IOException{

System.out.println("Enter any number:");

System.out.println("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);
}

getMoreCombinations(str);
}

}
}

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;

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;

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.

Thanks !
Re: Write a C program

@Shalini, i looked into the code. The problem is with the logic of function getMoreReducedFormCombinations.

As per the logic of the code:
1. The initial combination that you take consist of all i's (for i = 1 to N) and the remainder at the end.
2. You call getMoreReducedFormCombinations for each combination you get reduce the combination size till it contains only two numbers.
3. The logic to you used to reduce the combination size is either you sum up lats two numbers (if difference is <= 1) or subtract 1 from last digit and add 1 to second last digit.

You code work till N = 7 but skip some entries when N >= 8. Let's see why it creates problem for N >=8.

For N=8, the output should have been 22 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+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+4
```
Whereas, 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+3
```
The entries missing here are "1+1+2+2+2" and "1+2+2+3".

As per the logic of your code (what i mentioned in step 3 above), the combination size is reduced by manipulating only last two digits. But the logic does not take care that the combination can also be obtained by manipulating digits other then last two digits.

E.g., when you got combination "1+1+1+1+2+2", the code reduced it by adding the last two digits and giving a new combination "1+1+1+1+4" but a new combination can be obtained by adding third and fourth last digits as "1+1+2+2+2".

Similarly, when you got combination "1+1+1+2+3", the code reduced it by adding the last two digits and giving a new combination "1+1+1+5" but a new combination can be obtained by adding third and fourth last digits as "1+2+2+3".

The code only output those entries where except last two digits all other digits are always i's (for i = 1 to N) and any entry which does not follow this pattern (e.g., "1+1+2+2+2" and "1+2+2+3") will be missing.

Improving the logic of code to handle this will fix the issue.

shalini_goel14 • Jul 14, 2009
Cool man. I got it where I was going wrong. Will try it as soon as get some better time.

Thanks a lot !

PS: Still looking for a better logic. 😔
safwan • Jul 14, 2009
Re: Write a C program

arihant007
Guys 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.
I know many forums that say like same as you you might be knowing this but i know what you say is correct
why cant we give a logorithem in words adn then putting it on coding .
safwan • Jul 14, 2009
yes ! give me some more time just to get ridof exame and itill saturday ill post (as just to get logi and time)

Is VB alllowed ?
safwan
Is VB alllowed ?
You can post solution in any language of your choice.

mech_guy • Jul 15, 2009
Hi,

Here is my attempt. Am not good at programming in C++ (as can be seen from length of code and coding itself) , so i will appreciate all comments/critics from some of the cool programmers i have seen at CE.

```#include
#include

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= j) factorize(n1,j,a);
j = j + 1;
}
nfact1 = nfact2;
// cout << "Factors of " << i << endl;
for (int j=0; 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: 8
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
Code will be limited for numbers upto 22, else might have to increase size of arrays.

If there is a way out to know beforehand, the total combinations possible for a given number then it would be easier (to code and also cross-verify the answer).

Regards
Good work buddy, now we have one working code 😁

I have few suggestions:
1. I feel the cout and for loop at the end of main function should be inside the last else statement of the main function.
2. Avoid use of global variables, you will have many advantages (e.g., the code will be more reusable).
3. Running the code for N=22 gives error at the end of execution. This might be because for N=22 the total number of combinations are 558 and the array factor1 can hold only 512 entries. So you are writing on memory not allocated to the array. To avoid such issues use dynamic memory allocation.
4. The code has heavy use of string operations and large number of temporary variables which can be reduced, e.g.,
```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);
```
Below is my solution to the problem:

```#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:
a.exe < input.txt > output.txt [on windows]
a.out < input.txt > output.txt [on linux]

Here,
a.exe or a.out are the executables generated after compilation

input.txt is the file containing input, e.g., if the number is ‘5’ then input.txt will be:
5

output.txt is the output file containing result, for given example output.txt will contain:
Combinations:
0 + 5
1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 2
1 + 1 + 3
1 + 2 + 2
1 + 4
2 + 3
Total combinations: 7

@mech_guy

I was comparing the results of your code with the results of my code. Your code worked fine till N=10. But after that it skipped few entries, e.g.,

For N=11
The output of code was 55 combinations whereas the total combinatipns possible are 56 ("2 + 2 + 3 + 4" combination was missing in output).

mech_guy • Jul 20, 2009

Thanks a lot man for your comments. Will go through all (one by one) 😀

Thanks a lot again and would go through your comments and your code too (looks wow to me).

Any chance that we could know beforehand about "Total number of combinations" for a given number. Atleast if one knows that one could cross-verify his/her code.

Regards