Make a code have less Complexity

Question

3.00/5 (2 votes)

See more:

Coming straight from my last question and my thanks to @Andreas Gieriet I create a program in C that make the following procedure.

Giving a dynamic array with elemnts we want to make a procedure so we can find the lowest sum of the elements in the array.

So if we have that elements: 5 6 1 4 9 3 1 2

the procedure will be the following diagram.

http://prntscr.com/60l705[^]

And in the end we want the minimun of the weight values. In that case 13.

I created the code but i was wondering as the Complexity of the program is O(n^3) if there is any way to reduce it to O(n^2) even in O(N).

C

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>


int sum_array(int* array, int cnt)
{
    int res = 0;
    int i;
    for ( i = 0; i < cnt ; ++i)
        res += array[i];
    return res;
}

int main()
{
    FILE* input = fopen("share.in","r");

    int N = 0;
    fscanf(input,"%d",&N);

    int *array = (int*)malloc(N * sizeof(int));

    for (int i = 0; i < N; i++)
        fscanf(input,"%d",&array[i]);

    fclose(input);

    int Min = 0;
    int bestA = 0, bestB = 0, bestMin = INT_MAX;
    int A, B;
    int i;
    for ( A = 0; A < N - 2; ++A)
    {
        for ( B = A + 1; B < N - 1; ++B)
        {
            int ProfitA = sum_array(array, A + 1);
            int ProfitB = sum_array(array + A + 1, B - A );
            int ProfitC = sum_array(array + B + 1, N - 1 - B );

            //here the values are "current" - valid
            Min = (ProfitA > ProfitB) ? ProfitA : ProfitB;
            Min = (ProfitC > Min) ? ProfitC : Min;

            if( Min < bestMin )
                bestA = A, bestB = B, bestMin = Min;

        }
    }
    printf("%d\n", bestMin);
    free(array);
    return 0;
}

First think using Greedy Algorithm:

C#

int idx0 = 0;
int idx1 = 1;
int idx2 = N-1;

int sum0 = arr[0];
int sum1 = arr[1];
int sum2 = arr[N - 1];

int max = (sum0 > sum1) ? sum0 : sum1;
    max = (sum2 > Max) ? sum2 : Max;

for (i=0; i < N - 1; i++){
    sum += arr[i];
}


while ((idx1 + 1) < idx2) {
    const int left = (sum0 + arr[idx1]);
    const int right = (sum2 + arr[idx2-1]);

    if (left <= right && left <= max) {
        sum0 = left;
        sum1 -= arr[idx1++];
        max = (sum1 > sum2) ? sum1 : sum2; //left cannot be greater
    } else if (right < left && right <= max) {
        sum2 = right;
        sum1 -= arr[--idx2];
        max = (sum1 > sum2) ? sum1 : sum2; //right cannot be greater
    } else break;

    //something like return make_pair(idx[1],idx[2]);
    //and what I return? I return the value I want? The minimun one?

}

That is my question, if anyone has any idea post an answer!

Posted 3-Feb-15 4:58am

GeorgeGkas

Updated 3-Feb-15 6:26am

v2

Add a Solution

Comments

Zoltán Zörgő 3-Feb-15 11:26am

1) Are you sure it can be reduced?
2) It seems to be your homework, what about thinking a little bit yourself...?

[no name] 3-Feb-15 11:32am

well not. That was my homework and I solve it. I just though if I can reduce the complexity.

Zoltán Zörgő 3-Feb-15 11:38am

You can eventually...
1) start with the first (i=1) and last (j=N) element for A and C, summarize the rest in B
2) check what would happen if you add [i+1] to A or [j-1] to C - and choose the best direction, by increasing i or decresing j (and updating A, B and C)
3) continue until max(A,B,C) is not decreasing anymore
I am not absolutelly sure this will lead to the result you need, but the algorythm is like M optimization in linear programming
I will try to code it, if I get the time...

[no name] 3-Feb-15 11:44am

what if we use some greedy algorithm? Would be safe?

Zoltán Zörgő 3-Feb-15 11:55am

This is actually one. Safe? It would note eat up your fridge :D

[no name] 3-Feb-15 11:58am

I mean If I don't miss anything. Please if you can make an algorithm so I can check my vision with yours. And i also think that this will give me O(N).

[no name] 3-Feb-15 12:25pm

ok I make a silly C code. Is that the way I need to proceed? Am I right?

1 solution

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

**Zoltán Zörgő** · Accepted Answer · 2015-02-03T06:40:00

Solution 1

Here is the code of my approach:

C#

int max(int A, int B, int C)
{
    return Math.Max(A, Math.Max(B,C));
}

void Main()
{
    var e = new byte[] {5,6,1,4,9,3,1,2};
    var i=0;
    var j = e.Length-1;
    int A = e[i];
    int C = e[j];
    int B = 0;
    for(int x = i+1 ; x < j; x++) B+=e[x];
    var mp = int.MaxValue;
    var m = max(A,B,C);
    Console.WriteLine("A={0} B={1} C={2}", A, B, C);
    while(m < mp)
    {
        int AL = A+e[i+1];
        int CR = C+e[j-1];
        int BL = B-e[i+1];
        int BR = B-e[j-1];
        if(max(AL,BL,C) < max(A,BR,CR) )
        {
            A=AL;
            B=BL;
            i++;
        }
        else
        {
            C=CR;
            B=BR;
            j--;
        }
        mp = m;
        m = max(A,B,C);
        Console.WriteLine("A={0} B={1} C={2}  MAX={3}", A, B, C, m);
    }
    Console.WriteLine(mp);
}

Yes, it is C#, but quite easy to trasscribe it in C/C++, as it is not using any .NET specific. With the sample input you have given, it is terminating in 6 steps:

A=5 B=24 C=2
A=11 B=18 C=2  MAX=18
A=11 B=17 C=3  MAX=17
A=11 B=14 C=6  MAX=14
A=12 B=13 C=6  MAX=13
A=12 B=4 C=15  MAX=15
13

Check here: https://dotnetfiddle.net/LC92ZU[^]

Same thing in C :(

C

#include <stdio.h>
#include <limits.h>
#define max(A,B,C) A > (B > C ? B : C) ? A : (B > C ? B : C)
#define N 10

int main()
{
    int e[N] = {1, 1, 8, 1, 1, 3, 4, 9, 5, 2 };
    int i=0;
    int j = N-1;
    int A = e[i];
    int C = e[j];
    int B = 0;
    int x, AL, CR, BL, BR, m, mp = INT_MAX, L, R;
    for(x = i+1 ; x < j; x++) B+=e[x];
    m = max(A,B,C);
    printf("A=%d B=%d C=%d\n", A, B, C);
    while(m < mp)
    {
        AL = A+e[i+1];
        CR = C+e[j-1];
        BL = B-e[i+1];
        BR = B-e[j-1];
        L = max(AL,BL,C);
        R = max(A,BR,CR);
        if(L<R)
        {
            A=AL;
            B=BL;
            i++;
        }
        else
        {
            C=CR;
            B=BR;
            j--;
        }
        mp = m;
        m = max(A,B,C);
        printf("A=%d B=%d C=%d MAX=%d\n", A, B, C, m);
    }
    printf("%d", mp);
    return 0;
}

Online: http://ideone.com/v1NFTw[^]

Posted 3-Feb-15 6:40am

Zoltán Zörgő

Updated 3-Feb-15 9:36am

v4

Comments

[no name] 3-Feb-15 12:50pm

I knwo some basic things just to understand your code. This will work even with input 1.000.000?

Zoltán Zörgő 3-Feb-15 12:51pm

As long as it fits into memory

[no name] 3-Feb-15 12:54pm

I use that input 1, 1, 8, 1, 1, 3, 4, 9, 5, 2 and I took only the 5 outputs? Why I took wrong output?

[no name] 3-Feb-15 13:34pm

Sir I couldn't manage to solve it. What we make wrong?

Zoltán Zörgő 3-Feb-15 14:30pm

What? With 1, 1, 8, 1, 1, 3, 4, 9, 5, 2
The result is:
A=10 B=9 C=16 MAX=16

Zoltán Zörgő 3-Feb-15 14:31pm

I would be interested why I got the downvote :(

[no name] 3-Feb-15 14:46pm

well sory for the downvote but I have two points. First I wanted C code not C#. I try to make the code but it didn't worked. Secondly here is the diagram. http://prntscr.com/60ojdm if you see there is a 15! Try to fix that two and I will accept your answer!

Zoltán Zörgő 3-Feb-15 14:55pm

Dude,
First: I don't do your homework. I have given you a working solution (waaaaaay better than the one you had), which you can transform in C in 10 minutes.
Second: check your diagram yourself, it has two inputs mixed (rows 1-10 and 11-21), it makes no sense. So what should that diagram mean?

Zoltán Zörgő 3-Feb-15 15:35pm

See C code...
Check your "diagram"!

jeron1 3-Feb-15 16:30pm

You downvoted someone (the only one) trying to help you? That's just wrong, perhaps 'thanks' would be a better aternative.

[no name] 3-Feb-15 18:54pm

You are kidding aren't you? You are downvoting a guy who has made a huge effort to help you. Work it out.

[no name] 4-Feb-15 8:02am

you see I upvoted you and also accept your answer. But the question is still a mystery. With my input the minumun number is 15 not 16!

Zoltán Zörgő 4-Feb-15 8:10am

Which input exactly? And which should be the better combination not found by my algorithm? Might not be perfect, but don't tell 15 or 16, or whatever - tell me the groups of values giving that better result for that specific input.

[no name] 6-Feb-15 6:21am

well I show your code and I found the mistake. Every person MUST work at least ONE DAY. It cant be one not to work. In your program try 9,8,2,3 this input. You see the last output B is 0. It can't be 0 neither A nor C! That's what you need to fix! :)

Zoltán Zörgő 6-Feb-15 7:31am

First, I don't need to do/fix anything.
Second: with your input the program is not giving the result you say. You should have noticed, that not the last row is the final result, but the row before it. With 9,8,2,3 the output is:


A=9 B=10 C=3
A=9 B=8 C=5 MAX=9
A=9 B=0 C=13 MAX=13
9

As I mentioned before, the algorythm is stopping when MAX begins to increase. So the final result is the combination before that. But you never mentioned you need the combination, just the maximum, which is held in variable mp, and printed after exiting the loop. The rest is just for information.
I don't say that my solution is correct, but if you want to find an error, you should start to undertand the output at least... until now, you haven't found any input for which is giving incorrect result.
But as I mentioned before, this is your homework. Take it or lieve it.

Make a code have less Complexity

1 solution

Solution 1

Add your solution here

Preview 0

Make a code have less Complexity

1 solution

Solution 1

Add your solution here

Preview 0

Existing Members

...or Join us