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

Replies

parag_kulkarni

Re: Write a C program

Hi All,

I almost got the answer😁

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++;

}
}

}
}
pradeep_agrawal

Re: Write a C program

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

-Pradeep
shalini_goel14

Re: Write a C program

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

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

Anyone else ?
arihant007

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

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

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

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

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

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:

debu

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

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

Re: Write a C program

Solution in PHP, (I am loving this language 😀)

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 \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

Re: Write a C program

The post still remains open for C program
pradeep_agrawal
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).

-Pradeep
Sahithi Pallavi

Re: Write a C program

Hi everyone...I tried this program in C...but I am not successfull. can anybody pls help me....
pradeep_agrawal

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.

-Pradeep
uday.bidkar

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

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.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 additionCombinationsSet= new HashSet();
    
    
    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.

Thanks !

pradeep_agrawal
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.

-Pradeep
shalini_goel14

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

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

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 ?
pradeep_agrawal

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

-Pradeep

mech_guy

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

pradeep_agrawal
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);
```
-Pradeep

pradeep_agrawal

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

-Pradeep

pradeep_agrawal

@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).

-Pradeep
mech_guy

Hi Pradeep,

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

Yup, i got it. (2+2+3+4) must have been missed (never thought about this poor fellow).

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

You are reading an archived discussion.

Representing number as sum of smaller numbers

Replies

Related Posts

Think Simple, think business - Earn Rs. 15 lakh !

JBase Vs Java

hii - can anyone tell me more about CE?

MATLAB - makes life easier for Engineers

data processors