XOR of all Array components which can be excellent squares

[ad_1]

View Dialogue

Enhance Article

Save Article

Like Article

View Dialogue

Enhance Article

Save Article

Like Article

Given an array arr[] containing N integers, the duty is to search out the XOR of all the weather of this array which can be excellent squares.

Examples:

Enter: arr[] = {3, 9, 16, 12, 13, 15} 
Output: 25
Clarification: Solely 9, 16 are the right squares within the given array.
So the XOR of 9 and 16 is 25, XOR = 9 ^ 16 = 25

Enter: arr[] = { 3, 9, 12, 13, 15 } 
Output: 9
Clarification: Solely 9 is the right sq. so the reply will probably be 9.

Strategy: To unravel the issue observe the under thought:

With a purpose to discover the XOR of excellent sq. components within the array, merely iterate via the array and discover if a component is an ideal sq. or not, after which calculate the XOR utilizing. 

Observe the under steps to compute the reply: 

  • Declare a variable ( say xor_arr) to retailer the reply and initialize it to 0.
  • Iterate from the beginning of the array:
    • For every ingredient within the array, examine if it’s a excellent sq. or not.
      • A easy method to examine is that if the ceil and ground of the sq. root of a component are equal then the quantity is an ideal sq..
    • Discover the XOR of the right sq. ingredient and retailer it within the end result variable utilizing the ‘^’ operator.
  • Return the xor_arr variable that shops the XOR of all excellent sq. components within the array.

Beneath is the implementation of the above method.

Python3

  

import math

  

def checkperfectsquare(x):

      

    

    

    

    return math.ceil(math.sqrt(x)) == math.ground(math.sqrt(x))

  

def xorOfArray(arr, n):

      

    

    xor_arr = 0

      

    

    

    for i in vary(n):

          

        

        if checkperfectsquare(arr[i]):

            xor_arr = xor_arr ^ arr[i]

      

    

    return xor_arr

  

if __name__ == '__main__':

    arr = [3, 9, 16, 12, 13, 15]

    N = len(arr)

      

    

    print(xorOfArray(arr, N))

Time Complexity: O(N)
Auxiliary Area: O(1)

[ad_2]

Leave a Reply