Print if there is a number combination that equals the given number

user_14905794 0
Viewed 99

I had this question in my exam a few weeks ago (Failed to answer it) and I wanted to know how to solve this kind of questions because I see they repeat themselves.

Write C program that gets Integers till -1 is inserted. if certain product of previously written numbers is equal to the last entered integer - the program will print it.

I know its pretty hard to understand but here are few examples :
(Typed order left to right)
1 -> 2 -> 3 -> 6 (Will print 2 * 3=6) -> 36 (Will print 2 * 3 * 6) -> -1

I can see that the problem is hard to do with arrays because of the memory limitation... so I though of using "List" but ain't got idea how to.

I don't want a complete solution! I would like to get any hint on how to solve it in C (C# is also ok but C preferred).

list c algorithm
2 Answers
user_95743930

I wrote a raw program that does what you want with the exception that it always considers 1 as the product of previous numbers, and the same is true for numbers that were already entered. I leave you the challenge to fix the issue.

#include <stdio.h>

#define SIZE 10

void combo( int pro, int sum );

int n[SIZE], found, i;

int main() {

    for( ; i < SIZE && scanf("%d", &n[i]) == 1 && n[i] != -1; i++) {
        
        found = 0;
        
        combo(1,0);
        
        if( found ) printf("%d ", n[i]);
    }
    
    return 0;
}

void combo( int pro, int sum )
{
    if( pro == n[i] ) found = 1;
    
    for(int j = 0; j < i - sum && !found; j++) {
        
        combo(pro * n[j], sum + 1);
    }
}

n, found, i don't have to be global variables, but since combo could call itself lots of times, I thought it would have been a good idea to avoid giving it many arguments. I really don't know if it actually is a good idea.

Anyway, the program is a brute force. combo() will try every possible products of the elements of n.

For each j, combo will call itself generating a new loop, and for each index of this new loop there will be another recursive call generating a whole new loop, and so on.

combo stops to call itself when all the loops stop running.
A loop stops when either a matching product has been found or j reaches i - sum, where i is the current number of elements stored in the array minus 1, while sum represents the number of elements involved in the current product.

Every time, before to enter a loop, the function checks whether the current product matches the last number entered in the array.

If you know that the numbers are entered in ascending order you can optimize by swapping !found with pro < n[i].
I haven't done the math, but in case the input consists in a sequence of random integers, it may be more efficient to sort the array before to call combo in main.

user_141706860
Related