Home.... | log in.... | Pub my question! | Sign-up....

Java-index >> Other Topics >> Algorithms

seminegative array

hello!if you have an array that the first part contains negative numbers. what is the fastest way to count how many negative numbers in it?Meir!

[172 byte] By [038790804] at [2007-9-27 21:28:05]

«« Capturing all the text that I output to the console
»» Printing Components on a JPanel

# 1

Hmmmm... If this isn't a trick question... I don't think it matters whether the negative numbers are first or last or in the middle if they could appear anywhere. Of course, if you know they are the first three numbers, then your answer is three without any computation! Otherwise, this should do the trick:

int numberOfNegatives = 0;

for( int i = 0; i < sizeOfArray; i++ )

{

if( arrayName[ i ] < 0 )

numberOfNegatives++;

}

System.out.print( "The total number of negative numbers: " +

numberOfNegatives );

Good luck!

ArtVandelay at 2007-7-7 3:23:44 >

top of Java-index,Other Topics,Algorithms...

# 2

> Hmmmm... If this isn't a trick question... I don't

> think it matters whether the negative numbers are

> first or last or in the middle if they could appear

> anywhere. Of course, if you know they are the first

> three numbers, then your answer is three without any

> computation! Otherwise, this should do the trick:

> > int numberOfNegatives = 0;

> for( int i = 0; i < sizeOfArray; i++ )

> {

>if( arrayName[ i ] < 0 )

>numberOfNegatives++;

> }

> System.out.print( "The total number of negative

> numbers: " +

>numberOfNegatives );

> Good luck!

If you know that the negative numbers are at the beginning, then there should be a break or use a while:while(arrayName[i] < 0) {

numNeg++;

i++;

}

wywiwyg at 2007-7-7 3:23:44 >

# 3

> If you know that the negative numbers are at the

> beginning, then there should be a break or use a

> while:while(arrayName[i] < 0) {

>numNeg++;

>i++;

> }

or even better:

int i=0, n=0;

while(a[i] <0){

n++;

i++; }

ArtVandelay at 2007-7-7 3:23:44 >

# 4

> If you know that the negative numbers are at the

> beginning, then there should be a break or use a

> while

If you know that (a)the negative numbers are at the beginning and (b)that there are no positiv numbers between them you should use a binary search :

1. Look at the middle case

2. If negative, repeat with the rigth half, otherwise with the left half.

3. When your half is down to 1 element, the number of negative numbers is equal to the position where you are. Give or take 1, depending on the implementation.

This is the best, if you know only (a) and (b).

If you know (a) and (b) and have a good guess about how many numbers it might be, even better algorithms are possible.

If (b) is false, you have to stick with ArtVandelay.

phohmeyer at 2007-7-7 3:23:44 >

# 5

Hi!

int i, len=array.length;

for(i=0; i<len && array[i]><0; i++);

or if you sure that other elements are not negatives

int i;

for(int i=array.length-1; i>=0 && array[i]>=0; i--);

i = array.length-1 - i;

but 1st way is much pretty ;)

Regards, Alex

cebanenco at 2007-7-7 3:23:44 >

# 6

sweet code ceb. i like it. never thought of abusing a for loop like that. ; 0 )

ArtVandelay at 2007-7-7 3:23:44 >

# 7

> sweet code ceb. i like it. > never thought of abusing a > for loop like that. ; 0 )You can use it now ;) If you will add some dollars to me for that code - I will not be against :))

cebanenco at 2007-7-7 3:23:44 >

# 8

thank you for your answer, I do think that the binary search isthe fastest one, but what happens when you have only the first elementnegative?it means that its not so efficiant.what makes it better from scanning the array regularly?Meir.

038790804 at 2007-7-7 3:23:44 >

# 9

You can make algorithms more efficient if you have more information about your data. For example, if you know that only the first few entries are going to be negative, then a binary search may not be the best algorithm. Likewise if you know that almost all entries are negative, in which case you might want to scan from the end of the array backwards. But the original post implied no such knowledge.

DrClap at 2007-7-7 3:23:44 >

# 10

Actually, there is a trick that combines both advanteges of sequential and binary approach (it is used as an "unlimited"-sorted-arrays search - simply suppose that n which you can divide by 2 is not known)

1) step = 1, position = 0

2) found your result at [position+step]? (it's a bit tricky with positive/negative values, isn't it?)

3a) the value [position+step] is greater (or positive, in our case)

-> step = step/2

3b) the value [position+step] is lesser (or still negative)

-> position = position + step

step = step * 2

JirMac at 2007-7-7 3:23:44 >

Java programming resources: FAQs, tutorials, compiler and browser download sites, documentation, books lists, IDEs, etc.

seminegative array

Other Topics New Topic

Other Topics Hot Topic

Other Topics

All Classified