Thread: Different Logic to optimize this code further.

  1. #1
    Registered User
    Join Date
    Oct 2011
    Posts
    2

    Different Logic to optimize this code further.

    Given an array of size N i need to find sum of min numbers of the array which fall within a range.

    For eg: consider an array[ 1,2,3,4,5 ].i need to find sum of min numbersfrom this array which is greater than 5 and less than 8.
    Ans: since 1+5 is greater than 5 and less than 8 so the output is 2

    The way i solved the problem is this way.I checked if min number needed is 1 by using a for loop

    Code:
    for (i = 0; i < 5; i++)
         if (a[i] >= min && a[i] <= max)
            return 1;

    Then for checking if 2 is the min number

    Code:
    for (i = 0; i< 4; i++)
         for (j = i + 1; j < 5; j++)
            if (a[i] + a[j] >= min && a[i] + a[j] <= max)
                return 2;
    And so on...

    Code:
    for (i = 0; i < 3; i++)
         for (j = i + 1; j < 4; j++)
             for (k = j+1; k < 5; k++)
                 if (a[i] + a[j] + a[k] >= min && a[i] + a[j] + a[k] <= max) 
                     return 3;
    Code:
     for (i = 0; i < 2; i++)
         for (j = i + 1; j< 3; j++)
            for (k = j + 1; k< 4; k++)
                for (l = k + 1; l < 5; l++)
                    if (a[i] + a[j] + a[k] + a[l] >= min && a[i] + a[j] + a[k] + a[l] <= max)
                        return 4;
    And finally ...

    Code:
    if(a[0]+a[1]+a[2]+a[3]+a[4]>=min && a[0]+a[1]+a[2]+a[3]+a[4]<=max)
       return 5;
    Can any one suggest a more optimised way of solving this problem..

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Why is the answer 2? 1+2+3 = 6, which is between 5 and 8

    What does the "sum of min numbersfrom this array" actually mean?

    Oh, you want the minimum number of values that you can sum up in order to exceed 5.
    Perhaps you can spot where you can simply add another loop?
    Last edited by iMalc; 10-09-2011 at 12:16 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Oct 2011
    Posts
    2
    Thnks for the reply.Ya i want minimum number of values that can sum up in order to exceed 5 but not to exceed 8.

    Here is my function which return the min number of value...

    Code:
    int void CheckValue()
    {
    
    for (i = 0; i &lt; 5; i++) if (a[i] >= min && a[i] <= max) return 1;
    for (i = 0; i< 4; i++) for (j = i + 1; j < 5; j++) if (a[i] + a[j] >= min && a[i] + a[j] <= max) return 2; for (i = 0; i < 3; i++) for (j = i + 1; j < 4; j++) for (k = j+1; k < 5; k++) if (a[i] + a[j] + a[k] >= min && a[i] + a[j] + a[k] <= max) return 3;
    for (i = 0; i < 2; i++) for (j = i + 1; j< 3; j++) for (k = j + 1; k< 4; k++) for (l = k + 1; l < 5; l++) if (a[i] + a[j] + a[k] + a[l] >= min && a[i] + a[j] + a[k] + a[l] <= max) return 4;
    if(a[0]+a[1]+a[2]+a[3]+a[4]>=min && a[0]+a[1]+a[2]+a[3]+a[4]<=max) return 5; return 0; }
    Can u optimise this further or provide a better logic??

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How can i optimize this code
    By ArunS in forum C Programming
    Replies: 15
    Last Post: 08-08-2011, 02:11 PM
  2. Please help me optimize my code
    By lazyme in forum C++ Programming
    Replies: 3
    Last Post: 01-25-2010, 04:05 AM
  3. Replies: 6
    Last Post: 12-19-2007, 12:24 PM
  4. Wanna Optimize my code?
    By Echo in forum C++ Programming
    Replies: 10
    Last Post: 08-15-2005, 01:24 AM
  5. Sort strings in double linked list. (Optimize code)
    By netstar in forum C++ Programming
    Replies: 15
    Last Post: 02-28-2005, 01:40 AM

Tags for this Thread