baxy77bax has asked for the wisdom of the Perl Monks concerning the following question:

Hi,

I need some advice regarding the following problem.

Problem:

Let A be an array of integers where x,y is an index 0 < x,y < |A|-1. Given x find y  s.t. A[y] = z and A[y] is the first z-value element encountered starting from A[x] to A[y] where x>y .
Example:

A=[2 3 43 12 46 7 8 9 90 4 34 4 4]
Given that  x = 5 the  A[5] = 7 and given that  z =4 then  y=9. The problem is how to do this in constant time. How to preprocess the array A so that when x=5 and z=4 are given as an input result that is received is y=9. Does anyone have any suggestions ??
Cheers Baxy

UPDATE:

YES that is it , you see you got it :) : 

"Given an array A, an index i, and a value v,
find the smallest index j such that j > i and A[j] == v"

[download]
dave_the_m

UPDATE:2

well if it is a CS homework than please provide a solution because then i missed that class and therefore i don't know the solution and am a bit puzzled on how to get one. Plus, I don't want to do a Spares table for this

Replies are listed 'Best First'.
Re: Index finding problem
by dave_the_m (Monsignor) on May 13, 2012 at 12:16 UTC
    Your description is almost incomprehensible. Is the following what you actually meant?: 

    Given an array A, an index i, and a value v,
find the smallest index j such that j > i and A[j] == v

    [download]

    Dave.

[reply]
[d/l]
Re: Index finding problem
by BrowserUk (Patriarch) on May 13, 2012 at 14:20 UTC

    After preprocessing find() is O(1):

    #! perl -slw
use strict;
use Data::Dump qw[ pp ];

{
    my %V;
    sub preprocess {
        my $aRef = shift;
        push @{ $V{ $aRef->[ $_ ] } }, $_ for 0 .. $#{ $aRef };
        for my $v ( keys %V ) {
            my $last = 0;
            @{ $V{ $v } } = map{ 
                ( $_ ) x ( $_ - $last, $last=$_ )[0] 
            } @{ $V{ $v } };
            push @{ $V{ $v } }, (undef) x( @{ $aRef } - $last );
        }
    }

    sub find{
        my( $i, $v ) = @_;
        return $V{ $v }[ $i ];
    }
}

my @A = qw[ 2 3 43 12 46 7 8 9 90 4 34 4 4 ];
preprocess( \@A );

print "Next value 4 after position $_ is at: ",
    find( $_, 4 ) // 'none'
    for 0 .. $#A;
    
__END__
C:\test>970274
Next value 4 after position 0 is at: 9
Next value 4 after position 1 is at: 9
Next value 4 after position 2 is at: 9
Next value 4 after position 3 is at: 9
Next value 4 after position 4 is at: 9
Next value 4 after position 5 is at: 9
Next value 4 after position 6 is at: 9
Next value 4 after position 7 is at: 9
Next value 4 after position 8 is at: 9
Next value 4 after position 9 is at: 11
Next value 4 after position 10 is at: 11
Next value 4 after position 11 is at: 12
Next value 4 after position 12 is at: none

    [download]
    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

    The start of some sanity?
[reply]
[d/l]
Re: Index finding problem
by Anonymous Monk on May 13, 2012 at 12:20 UTC
    this sounds like it's a homework problem from a CS class.
[reply]

Back to Seekers of Perl Wisdom