Results 1 to 9 of 9
  1. #1
    Java2012 is offline Member
    Join Date
    Jun 2012
    Posts
    6
    Rep Power
    0

    Default A magnitude pole of an array problem

    Hello all;

    The problem is to find the magnitude pole of an array:

    "A magnitude pole of an array A consisting of N integers is an index K such that all elements with smaller indexes have values lower or equal to A[K] and all elements with greater indexes have values greater or equal to A[K], i.e.
    For example:
    5 is a magnitude pole of array A such that
    A[0]=4, A[1]=2, A[2]=2, A[3]=3, A[4]=1, A[5]=4, A[6]=7, A[7]=8, A[8]=6, A[9]=9."




    I need to figure out why this solution does not work:


    Java Code:
    public int magnitudePole(int[] A)
      {
        boolean foundLeft = true;
         
         boolean foundRight = true;
         
    
      
        for(int i = 0; i < A.length; i++)
        {
    
          
            for(int j = i - 1; j >= 0; j--)
            {
                if((A[i] - A[j]) < 0 )
                {
                   foundLeft = false;
                    break;
                }
                else
                {
                   foundLeft = true;
                }
               
            }
              
            for(int j = i + 1; j < A.length && foundLeft; j++)
            {   
                if((A[j] - A[i]) < 0)
                {                
                    foundRight = false;
                    
                    break;
                   
                }
            }          
            if(foundLeft && foundRight)
            {
                return i;
                
                
            }
             
        }
      
        return -1;
      }


    Thank you for your help.

  2. #2
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    4,017
    Rep Power
    10

    Default Re: A magnitude pole of an array problem

    How doesn't it work? What do you expect it to do? What does it do instead? You need to step through this with a debugger, or at the very least add some print statements, until you understand exactly what the program is doing.
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  3. #3
    Java2012 is offline Member
    Join Date
    Jun 2012
    Posts
    6
    Rep Power
    0

    Default Re: A magnitude pole of an array problem

    Thank you for your help. With this example :


    A[0]=4, A[1]=2, A[2]=2, A[3]=3, A[4]=1, A[5]=4, A[6]=7, A[7]=8, A[8]=6, A[9]=9."

    It should give 5 , but it gives -1.

    I went through every element on paper and it must work, I printed some values , but it does not help much.

    Any help?

  4. #4
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    4,017
    Rep Power
    10

    Default Re: A magnitude pole of an array problem

    Like I said, you'll have to step through this with a debugger, or at least add more print statements, until you figure out what's going on.
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  5. #5
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,816
    Rep Power
    25

    Default Re: A magnitude pole of an array problem

    It would help us to understand what the code is trying to do if you added comments to it describing what each part of the code is doing.
    If you don't understand my response, don't ignore it, ask a question.

  6. #6
    Ksharp is offline Banned
    Join Date
    Jun 2012
    Location
    Beijing,China
    Posts
    34
    Rep Power
    0

    Default Re: A magnitude pole of an array problem

    Your code looks good.But you need to check it more ,especial for your logic.

    Java Code:
    
    
    
     
     
    public class x{
     
        public static void main(String [] args)  {
        int[] A={4,2,2,3,1,4,7,8,6,9};
        boolean foundLeft ;
        boolean foundRight ;
        boolean found=false;
    
        for(int i=1;i< A.length-1;i++) {
         foundLeft = true;
         foundRight = true;
          for(int j=0;j<i;j++){ 
                               if (A[j] > A[i]) foundLeft=false;
                              }
          for(int k=i+1;k<A.length;k++){ 
                               if (A[i] > A[k]) foundRight=false;
                              }
        if (foundLeft && foundRight)  {System.out.println("Found it: " + i);found=true;}
                                        }
        if ( ! found ) System.out.println("Not Found.");
        
         
      }
    
     
    }


    Ksharp

  7. #7
    Java2012 is offline Member
    Join Date
    Jun 2012
    Posts
    6
    Rep Power
    0

    Default Re: A magnitude pole of an array problem

    Well I used your two advices printing statements, and checking every part. The problem in the code was, it should reset foundRight to true in the end of the main loop. So the code after the correction:



    Java Code:
    public  int magnitudePole(int[] A)
      {
         boolean foundLeft = true;
         
         boolean foundRight = true;
         
        //loop over each element and break the loop when you find the correct answer
         
        for(int i = 0; i < A.length; i++)
        {
            
     //check all the left elements of the current element
    
    
            for(int j = i - 1; j >= 0; j--)
            {
                if((A[i] - A[j]) < 0 )
                {
                   foundLeft = false;
                  
                    break;
                }
                else
                {
                    
                    
                   foundLeft = true;
                }
               
            }
          
       
       //if the all the left elements less than the current one check all the right elements of the current element
            
            for(int j = i + 1; j < A.length && foundLeft; j++)
            {   
                if((A[j] - A[i]) < 0)
                {                
                    foundRight = false;
                    
                    break;
                   
                }
            }
           
           //if all the left elements less than the current element
          //and if all the right elements bigger than the current element
         // return the index of the current element
            if(foundLeft && foundRight)
            {
    
                return i;
                
                
            }
    
    //the killing mistake was   foundRight should be reset to true   
    //and this was what made the code give the wrong answer even though the method is correct  
      
            foundRight = true;
        }
      
        return -1;
       
      }

    Ok! thank you guys for your help.

    Done!

  8. #8
    shukla2009 is offline Rahul Shukla
    Join Date
    Apr 2013
    Location
    Pune India
    Posts
    1
    Rep Power
    0

    Default Re: A magnitude pole of an array problem Solution with O(n) time complexity

    public int magnitudePole2(int[] A) {

    int[] max = new int[A.length];
    int[] min = new int[A.length];
    int mx = Integer.MIN_VALUE;
    int mn = Integer.MAX_VALUE;
    for (int i = 0; i < A.length; i++) {
    if (A[i] > mx)
    mx = A[i];
    max[i] = mx;
    }
    min[A.length - 1] = mn;
    for (int i = A.length - 1; i > 0; i--) {
    if (A[i] < mn)
    mn = A[i];
    min[i - 1] = mn;
    }
    for (int i = 0; i < A.length; i++) {
    if (A[i] >= max[i] && A[i] < min[i])
    return i;

    }
    return -1;
    }

  9. #9
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,732
    Blog Entries
    7
    Rep Power
    21

    Default Re: A magnitude pole of an array problem

    The OP already found a solution more than a year ago; I'm closing this thread.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. A problem with using an array
    By Czuks in forum New To Java
    Replies: 5
    Last Post: 12-21-2011, 06:11 PM
  2. Replies: 0
    Last Post: 05-12-2011, 08:04 PM
  3. Array Problem
    By Aiquoc in forum New To Java
    Replies: 6
    Last Post: 03-29-2011, 05:03 AM
  4. array problem
    By aizen92 in forum New To Java
    Replies: 26
    Last Post: 12-21-2010, 06:42 AM
  5. array problem
    By jabo in forum New To Java
    Replies: 2
    Last Post: 03-31-2010, 10:54 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •