majority element

[jury]

hy!!!!i am trying to write a java code that returns the majority element in an array and -1 if not!!this is what i came with

public class Majority{
 public static int arrMajority1(int A[]){
  int n = A.length;
  int c = 1;
  for(int i=0;i>A.length;i++){

    for(int j=i+1;j<A.length;j++)
     if (A[i]==A[j])
      c=c+1;
      if (c>(A.length/2)){
      return A[i];
      }
     }
     return -1;
    }
    public static void main(String[] args){
     int A[] = new int [] {50,50,100,500,1000,1500,3000,5000,7500,10000,12000,15000,17000,20000,25000,30000,35000,40000};
    // int arrMajority1 = A[0];
     System.out.println(" " + arrMajority1(A));
    }
}

[NormR1]

What is a "majority" element?

Can you explain what the problem is with the posted code? Does the code compile and execute without errors? What does the program print out? What should it print out?

Have you tried debugging the code by adding println statements to print out the values that the code is looking at and to show where the execution flow goes? If you see the values that the program sees when it executes, you should be able to see what is wrong with the logic.

[jury]

A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).it compiles and executes with no error,and returns -1 e.g given an array of {1,2,3,3,4,5} shuold return 3 and if {1,2,3,4,5} shuld return -1

[Starstreak]

So c is a counter? (why not call it that) Is it supposed to be keeping a tally on a specific array element?

BTW. n is not used.

[jury]

@startreak yah!!!help plizz

[NormR1]

Can you describe the algorithm you are trying to use to find the number?
An algorithm is a list of steps the code should take. You need to define the algorithm before you try writing the code. Writing code first is a waste of time.

BTW What is the correct answer for the array in the posted code?

[jury]

MAJORITY1(A)
1 n = A. length // Assume array is indexed from1
2 c = 1
3 for i = 1 to n −1
4 c = 1
5 for j = i +1 to n
6 if A[i ] == A[ j ]
7 c = c +1
8
9 if c > n
2
// Assume integer division
10 return A[i ]
11 return −1

[NormR1]

That's code, not a description of the algorithm.

I think your example is wrong:

array of {1,2,3,3,4,5} shuold return 3

there are 2 3s in the array. n=6, 6/2 = 3, 3+1 = 4 => There would have to be 4 3s

I don't think you have given the code an array with a majority element to detect. Try testing it again with a better array.

[Nutster]

Your for loop starting at line 5 will never be executed. You have the wrong condition. You need to reset c to 0 at the start of each main loop. At line 6, put c=0; You do not have to initalize c because it is getting reset right away. I do not like using post-increment when it is not needed; preincrement is slightly better, performance-wise. The variable n is never used; remove its declaration.

Revised code lines 3-6

int c;

for(int i=0; i < A.length; ++i)
{
    c=0;

Your function appears to be looking for the value that occupies more than half the elements of the array. If you just want the mode (the value that appears tht most), you would want:

public class Majority{
    public static int arrMode(int A[]){
        int nMode = -1;
        int nModeCount=0;
        int c;

        for(int i=0;i>A.length;i++)
        {
            c=0;
            for(int j=i+1;j<A.length;j++)
                if (A[i]==A[j])
                    c=c+1;
            if (c>nModeCount)
            {
                nMode = A[i];
                nModeCount = c;
            }
        }
        return nMode;
    }
};

This will give -1 as a "I did not find anything!" value, but that could be the most frequent value. Maybe throw an exception if there is no mode. If multiple values appear the most (each of them appears 4 times, for example), then this only returns the first.