How to implement below pseudocode in python with one class and three definitions

Question

How to implement below pseudocode in python with one class and three definitions:

Assume there is an array Ali...nl that stores n integer values. The range of integers lies in between 0 to k. Consider the following algorithm to determine number of integer lies in any particular range a and b Count (A) 1. Declare two new arrays B[0...k] an C[0...k 2. Initialize all elements of BO array with 0. //Now, use for loop to make increment in CO array counter respective to elements of A array. It will take o(n) time to process n elements of A array 3. for i 1 to A-length lluse for loop to store count up to jth element of BO array. It will take o(k)time to process k elements of BI array. 6. for j 1 to k

Explanation / Answer

class Pr4( object ):
        def __init__( self, A ):
                self.array = A;

        def preprocess( self ):
                #find k
                maxNumberSoFar = 0;
                for num in self.array:
                        if( num > maxNumberSoFar ):
                                maxNumberSoFar = num;
                self.k = maxNumberSoFar;
                #initialize B and C
                B = [0]*(self.k+1);
                C = [0]*(self.k+1);
                for i in range(len(self.array)):
                        B[ self.array[i] ] = B[ self.array[i] ] + 1;

                #initialize C
                C[0] = B[0];
                for j_ in range( self.k ):
                        j = j_ + 1
                        C[ j ] = B[j] + C[j-1];
                #store C as self variable, as it is needed for queries later
                self.C = C;

        def query( self,a , b):
                #adjust query variables
                if( a < 0 ):
                        a = 0;
                if( b > self.k ):
                        b = self.k;
                #if invalid input, return 0
                if not( a <= b ):
                        return 0;
                #give the result
                subtract = 0;
                if a<> 0:
                        subtract = self.C[a-1];
                return self.C[b] - subtract;

array = [1,4,3,2,1,3,5,6,2,3,1,2,4,5,6,1,8,2,0];
o = Pr4( array );
o.preprocess();
print o.query(0,5);

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.