0

I have array of int[10000].

I need to sum each int with other one, and show result, for only those, where sum are > N.

Sum, can be any with any element of array, also sum of 5,6,7...10000 elements of array which > N.

I can write down(all combinations, but it`s insane) it like a[1] + a[2] + a[3]... But may be there are other resolution?

I need result all combinations, that gives me sum which is >N

Okey. If it is array of int[10]?

Sklivvz
  • 30,601
  • 24
  • 116
  • 172
Konstantins K
  • 19
  • 5
  • 1
    "each int with other one"... sorry, can you clarify? are you looking for a 10000x10000 compare of `a[x]+a[y]`, testing each pair for > N? or what? what is the thing being summed? the entire array? all pairs? all triples? all combinations? or...? – Marc Gravell Oct 21 '12 at 21:43
  • 1
    This seems like homework, in that you have defined a problem but show no solution. Homework has been deprecated here, and is not valid as a question. Please write up your attempt to create a solution to this problem and then ask a question if you get stuck or encounter a technical issue in your program. – Travis J Oct 21 '12 at 21:43
  • 1
    Have you tried something?What should be the output when you find a sum that is greater than N? – Nikola Davidovic Oct 21 '12 at 21:43
  • All combinations. I think the best is to use Combinatorics theorems... – Konstantins K Oct 21 '12 at 21:51
  • @user1763833 you want to use all combinations on a 10,000 array? er.... have you done the math to see how large that is? It is *quite staggeringly* large. – Marc Gravell Oct 21 '12 at 21:55
  • 1
    What are you trying to do, really? There are around 2*10^3010 combinations that you can make of the numbers in the array, so you can't test them all. All the combined computer power in the world couldn't do that in your lifetime... – Guffa Oct 21 '12 at 21:59
  • @Guffa I'm thinking more like "universal heat death" ;p Also: what calculator do you use? most of my usual "go to" apps died for that! – Marc Gravell Oct 21 '12 at 22:01
  • @MarcGravell: calc.exe in Windows 8... – Guffa Oct 21 '12 at 22:02
  • @Guffa that's odd... I'm on win 8 x64, and it just says "Overflow". Or did you use logarithms? – Marc Gravell Oct 21 '12 at 22:03
  • @MarcGravell: There are 2^10000 possible combinations (except a few that should be excluded, i.e. the one with none of the items, and all of the ones with only a single item, so that's 10001 to subtract, but that won't make a noticable difference to the result). – Guffa Oct 21 '12 at 22:08
  • @Guffa dammit, I'm a bit-shitfter at core, and it didn't occur to me to think of it as a bit mask. Which is odd, 'cos whenever I've implemented manually, I've done it **exactly** as a bitmask! – Marc Gravell Oct 21 '12 at 22:09
  • Okey... if Array is int[10]... ? – Konstantins K Oct 21 '12 at 22:12
  • @user1763833: Then there are only 2^10 combinations, i.e. 1024 (minus the 11 ones that have zero or one items). You can check them all in a fraction of a second. – Guffa Oct 21 '12 at 22:14
  • @Guffa: I need to know, all variants where >N. Like Result: a[1] + a[5], a[1] + a[5] + a[6]. Not only possible combinations. – Konstantins K Oct 21 '12 at 22:20
  • Even at n = 10 this is nasty. – Travis J Oct 21 '12 at 22:22
  • @TravisJ at n=10, I wouldn't blink at it - I'd just implement it. Probably brute force (nothing clever) – Marc Gravell Oct 21 '12 at 22:23
  • @TravisJ: Yeap.. But "R" statistics can do this.. – Konstantins K Oct 21 '12 at 22:24
  • There are 10000! possible combinations. Factorial, that's a Big Number. Self-training on the limits of computability is difficult if it isn't obvious. – Hans Passant Oct 21 '12 at 22:33
  • @user1763833: Just loop through the possible combinations and calculate the sum for each, and keep the ones that you like. – Guffa Oct 21 '12 at 22:44
  • @Guffa: So i need, to write in my code, all possible combinations? Not the best way... – Konstantins K Oct 21 '12 at 22:49
  • @HansPassant: But a[1]+a[2] is the same as a[2]+a[1], so you get a lot of duplicates. When you have elliminated those, there are only 2^10000-10001 combinations left. – Guffa Oct 21 '12 at 22:49
  • @user1763833: That depends on what you want to do. That's the simplest way, so that is the best way in one aspect. – Guffa Oct 21 '12 at 22:50

1 Answers1

1

Your problem is similar to Subset Sum problem. Here you can find two solutions for this algorithm. The only change is you have to track your numbers whose sum is greater that N and you need to repeat it for all possibilities instead of just finding true/false result.

Community
  • 1
  • 1
manman
  • 4,743
  • 3
  • 30
  • 42