# C++ Data Structure Problem

Sorted Vector

----------------

class SortedVector{

public:

// adds myVal to the SortedVector. duplicates are allowed, so myVal is always added

double get(i);

// pre: i < number of values in the SortedVector.

// post: return is the value in position i (position 0 holds the smallest value).

int size(); //returns the number of elements currently in the SortedVector

private:

//.....

};

Implement this class however you can so that each add or get is fast. The class is called SortedVector because it allows you to keep adding values to it, and it behaves as if it keeps them in a vector sorted in ascending order -- [url removed, login to view](3) returns the value that would be in myVec[3].

Here is a test program with some test cases:

a=10 p=17 n=10 ==> 12 ,10 were placed in position 10

a=10 p=100,000,007 n=522 ==> 92884289 was placed in position 522

a=10, p=100,000,007 n=520 ==> 94387374, 58959785 were placed in position 520

a=10, p=17, n=100,000 ==> 16 was placed in position 100,000 at least 20 times

int main(){

cout<<"enter a,p,n "; int a,p,n; cin>>a>>p>>n;

cout<<"storing "<<n<<" values into the SortedVector"<<endl;

SortedVector sv; int val = 1;

for(int i=0; i<n; i++){

val = a*val%p; [url removed, login to view](val);

}

cout<<"finished "<<n<<" adds. Now will add and get "<<n<<" times"<<endl;

int ct=0;

for(int i=0; i<n; i++){

val = a*val%p; [url removed, login to view](val);

if( [url removed, login to view](n)==val && ct++<20 ) cout<< val << " was placed in position "<<n<<endl;

}

return 0;

}

REQUIREMENT: if n is 100,000 this program should finish in less than 30 seconds after entering a,p,n.

## Deliverables

1) I need the problem solved with an efficient algorithm involving data structures so it will complete in a reasonable amount of time.

2)All lines of code must be commented. The program must be run from debug mode within Visual C++ Studio (6.0 or higher).

3)Before coding, please describe how you plan to complete the problem and what algorthims and data structures you plan on using.

## Platform

WindowsXP, Visual C++ Studio 6.0( or equiv)

( 2 comentários ) United States

ID do Projeto: #2965069

## Premiar a:

mihaidanila

See private message.

\$2 USD em 5 dias
(12 Avaliações)
3.3

## 15 freelancers estão ofertando em média \$11 para este trabalho

mihaiscortaru

See private message.

\$10.2 USD in 5 dias
(160 Comentários)
6.0
emilianbold

See private message.

\$8.5 USD in 5 dias
(77 Comentários)
5.8
projetcoder

See private message.

\$17 USD in 5 dias
(39 Comentários)
5.0

See private message.

\$17 USD in 5 dias
(68 Comentários)
4.8
vw821235vw

See private message.

\$8.5 USD in 5 dias
(94 Comentários)
4.3
lalesculiviu

See private message.

\$17 USD in 5 dias
(18 Comentários)
4.2
teamvw

See private message.

\$17 USD in 5 dias
(36 Comentários)
3.8
vw472664vw

See private message.

\$6.8 USD in 5 dias
(37 Comentários)
3.0
vasilevalaiba

See private message.

\$17 USD in 5 dias
(9 Comentários)
2.5
codepvw

See private message.

\$10.2 USD in 5 dias
(9 Comentários)
2.6
gurux

See private message.

\$11.05 USD in 5 dias
(4 Comentários)
2.7
blabbone

See private message.

\$17 USD in 5 dias
(1 Comentário)
1.9
bruce1970

See private message.

\$4.25 USD in 5 dias
(5 Comentários)
1.7
vw914040vw

See private message.

\$5.95 USD in 5 dias
(16 Comentários)
1.6