Sum of Numbers - XOR and OR

PKJ

 Coding Problem Keys 

 Sum of Numbers - XOR and OR 

 Problem Statement 

In the faculty of Informatics Engineering, the Teacher of Mathematics gave a lecture on bits and explained XOR and OR.

Then he decided to test the competence of his students by giving them this question. He will give the students an array A of N numbers and then give them Q queries.

Each query will consist of three numbers Typeᵢ, Lᵢ and Rᵢ. Each of the queries can be one of the following types.

    - If Typeᵢ is 1, then the student has to replace each Aᵢ with (Aᵢ | (Aᵢ - 1)) for every i between Lᵢ and Rᵢ.
    - If Typeᵢ is 2, this means that the student must replace each Aᵢ with (Aᵢ ^ (Aᵢ - 1)) for each i between the Lᵢ and Rᵢ.

After each query, the professor asks his students to calculate the sum of the numbers from array A. You need to find the sum of the answers to all the queries modulo 10^9+7.

Note

  • The sign | represents the logical OR.
  • The sign ^ represents the logical XOR.

 Function Description 

Complete the Solve function in the editor. It has the following Parameter(s):
Parameters
    - N (INTEGER) - The length of the array A.
    - Q (INTEGER) - Number of queries.
Return
    - The function must return an INTEGER denoting the sum of the numbers from array A.

 Constraints 

1 ≤ N ≤ 10⁵
1 ≤ Q ≤ 10⁵
1 ≤ A[i] ≤ 10⁵
1 ≤ Type[i] ≤ 2
1 ≤ L[i] ≤ N
1 ≤ R[i] ≤ N

 Input Format For Custom Testing 

The first line contains an integer, N, denoting the number of elements in A.
The next line contains an integer, Q, denoting the number of the query (the number of the elements in array Type, L and R).
Each line i of the N subsequent lines (where 0 ≤ i ≤ N) contains an integer describing A[i].
Each line i of the Q subsequent lines (where 0 ≤ i ≤ Q) contains an integer describing Type[i].
Each line i of the Q subsequent lines (where 0 ≤ i ≤ Q) contains an integer describing L[i].
Each line i of the Q subsequent lines (where 0 ≤ i ≤ Q) contains an integer describing R[i].

 Sample Input/Output 1 

 Input 

4
1
1
2
3
4
1
2
3

 Output 

11

 Explanation 

The array will become [1, 3, 3, 4].

 Sample Input/Output 2 

 Input 

4
1
1
2
3
4
2
2
3

 Output 

9

 Explanation 

The array will become [1, 3, 1, 4].

 Sample Input/Output 3 

 Input 

4
2
5
4
8
6
1
2
1
2
3
2

 Output 

60

 Explanation 

After the first query, the array will become [5, 7, 15, 6], after the second query, the array will become [5, 1, 15, 6].

 Solution 

 Programming Language: Python 3 Language 

n=int(input())
q=int(input())
a=[];l=[];r=[];typ=[]
for i in range(n):
    a.append(int(input()))
for i in range(q):
    typ.append(int(input()))
for i in range(q):
    l.append(int(input()))
for i in range(q):
    r.append(int(input()))
b=[]
b.extend(a)
for i in range(q):
    if(typ[i]==1):
        for j in range(l[i]-1,r[i]):
            # Store OR of a[j] and a[j-1] in a[j]
        if(i!=q-1):
            b=[]
            b.extend(a)
    if(typ[i]==2):
        for k in range(l[i]-1,r[i]):
            # Store XOR of b[k] and b[k]-1 in b[k]
        if(i!=q-1):
            a=[]
            a.extend(b)
if 1 in typ and 2 in typ:
    # PRINT the sum of sum of a and sum of b
elif(1 not in typ):
    # PRINT the sum of b
elif(2 not in typ):
    # PRINT the sum of a

# Published By PKJCODERS

 (Note: Incase If the code doesn't Pass the output kindly comment us with your feedback to help us improvise.) 

Comments

Post a Comment

Popular Posts

Count Number of Occurrences of a Character

PKJ
 Count Number of Occurrences of a Character   Problem Statement:  The program must accept a string S and a character CH as the input. The program must print the number of occurrences of CH in the string S as the output.  Boundary Condition(S):  1 <= Length of S <=1000  Input Format:  The first line contains the string S. The second line contains the character CH.  Output Format:  The first line contains the number of occurrences of CH in the string S.  Example Input/Output 1:   Input:  pineapple p  Output:  3  Explanation:  The character p has occurred three times in the string " p inea pp le". So 3 is printed as the output.  Example Input/Output 2:   Input:  Encyclopedia e  Output:  1 Explanation: The character e has occurred only once in the string "Encyclop e dia". So 1 is printed as the output. Example Input/Output 3: Input: KEYBOARD y Output: 0  Note: M...
Click to Continue...

Print Prime Numbers from 2 to N

PKJ
 Coding Problem Keys   Print Prime Numbers from 2 to N   Problem Statement  The program accepts an integers N as the input. The program must print all the prime numbers from 2 to N (inclusive of N) as the output.  Input Format  The first line contains the value of N.  Output Format  The first line contains all the prime numbers from 2 to N.  Boundary Condition(s)  2 <= N <= 999999  Example Input/Output 1   Input  11   Output  2 3 5 7 11  Example Input/Output 2   Input  120  Output  2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113  Max Execution Time Limit: 3000 millisecs   Solution   Programming Language: Python 3 Language  n= int ( input ()) l=[ True for i in range (n+ 1 )] j= 2 while (j*j<=n): if l[j]== True : for i in range (j*j,n+ 1 ,j):l[i]= False j+= 1 ...
Click to Continue...

Cities and Population

PKJ
 Coding Problem Keys   Cities & Population   Problem Statement  The program must accept the name and population of N cities as the input. The program must print the total population in the given N cities as the output. Then the program must print the name and population of each city separated by a colon as the output.   Example Input/Output 1   Input  3 KKTCity 19000 URCity 81000 MCCity 21000  Output  121000 KKTCity:19000 URCity:81000 MCCity:21000  Explanation  Here N = 3 and the total population in the given 3 cities is 121000. Hence the output is 121000 KKTCity:19000 URCity:81000 MCCity:21000  Example Inpu...
Click to Continue...

K Palindrome Integers

PKJ
 Coding Problem Keys   K Palindrome Integers   Problem Statement  The program accepts two integers  N  and  K  as the input. The program must print the first K palindrome integers greater than N as the output.  Input Format  The first line contains the value of N and K separated by a space.  Output Format  The first line contains K integers representing the first K palindrome integers greater than N.  Boundary Condition(s)  1 <= N <= 10 ⁷ 1 <= K <= 1000  Example Input/Output 1   Input  1221 5   Output  1331 1441 1551 1661 1771   Explanation  Here N = 1221 and K = 5. The first 5 palindrome integers greater than 1221 are 1331, 1441, 1551, 1661 and 1771 . Hence the output is 1331 1441 1551 1661 1771  Example Input/Output 2   Input  658100 10  Output  658856 659956 660066 661166 662266 663366 664466 665566 666666 667766  Max E...
Click to Continue...

Most Vowels in Row

PKJ
 Most Vowels in Row   Problem Statement:  The program must accept a character matrix of size NxN as the input. The program must print the row which contains most number of vowels in it. If more than one row has same number of most number vowels then print the last occurring row. Boundary Condition(s): 1 <= N <= 50 Input Format: The first line contain N. The next N lines contain N characters each separated by a space. Output Format:  The first line contains  C characters.  Example Input/Output 1:   Input:  5 G w w t e H d E o P Z D H e W Z l H e A H o O D e  Output:  H o O D e Explanation: The last two rows have 3 vowels. So the last occurring row with most number of vowels is the last row. Example Input/Output 2: Input: 4 w y o o g g t t t o e t a q r q Output: t o e t  Note: Max Execution Time Limit: 4000 millisecs  Solution:   Programming Language: C Language  #include <stdio.h> #include ...
Click to Continue...

Sum - Odd Number of Digits

PKJ
 Coding Problem Keys   Sum - Odd Number of Digits   Problem Statement  The program must accept N integers as the input. The program must print the sum of integers having odd number of digits in the given N integers. If there is no such integer, the program must print -1 as the output.  Boundary Condition(S)  1 <= N <= 100 1 <= Each integer value <= 10 ⁹  Input Format  The first line contains N. The second line contains N integers separated by a space.  Output Format  The first line contains the sum of integers having odd number of digits in the given N integers or -1.  Example Input/Output 1   Input  5 12 488 1 78 200  Output  689  Explanation  The integers with odd number of digits are 488 , 1 and 200 . So their sum is 689 (488 + 1 + 200).  Example Input/Output 2   Input  4 98 45 5000 11  Output  -1  Note: Max Execution Time Limit: 500 m...
Click to Continue...