Horje
XOR of all Array elements that are perfect squares

Given an array arr[] containing N integers, the task is to find the XOR of all the elements of this array that are perfect squares.

Examples:

Input: arr[] = {3, 9, 16, 12, 13, 15} 
Output: 25
Explanation: Only 9, 16 are the perfect squares in the given array.
So the XOR of 9 and 16 is 25, XOR = 9 ^ 16 = 25

Input: arr[] = { 3, 9, 12, 13, 15 } 
Output: 9
Explanation: Only 9 is the perfect square so the answer will be 9.

Approach: To solve the problem follow the below idea:

In order to find the XOR of perfect square elements in the array, simply iterate through the array and find if an element is a perfect square or not, and then calculate the XOR using. 

Follow the below steps to compute the answer: 

  • Declare a variable ( say xor_arr) to store the answer and initialize it to 0.
  • Iterate from the start of the array:
    • For each element in the array, check if it is a perfect square or not.
      • A simple way to check is if the ceil and floor of the square root of an element are equal then the number is a perfect square.
    • Find the XOR of the perfect square element and store it in the result variable using the ‘^’ operator.
  • Return the xor_arr variable that stores the XOR of all perfect square elements in the array.

Below is the implementation of the above approach.

C++

// C++ program to find the XOR of all elements in the array
// which are perfect squares
#include <bits/stdc++.h>
using namespace std;
 
// Function to find whether an element is perfect square
// or not
bool checkperfectsquare(int x)
{
    // If ceil and floor are equal the number is a
    // perfect square
    return ceil(sqrt(x)) == floor(sqrt(x));
}
 
int xorOfArray(int arr[], int n)
{
    // Stores final result
    int xor_arr = 0;
 
    // Iterating through every element in the array
    for (int i = 0; i < n; i++) {
 
        // Find XOR with the result
        if (checkperfectsquare(arr[i])) {
            xor_arr = xor_arr ^ arr[i];
        }
    }
 
    // Return the XOR
    return xor_arr;
}
 
// Driver Code
int main()
{
    int arr[] = { 3, 9, 16, 12, 13, 15 };
    int N = 6;
 
    // Function call
    cout << xorOfArray(arr, N);
    return 0;
}
 
// This code is contributed by Rohit Pradhan

Java

// Java program to find the XOR of all elements in the array
// which are perfect squares
import java.io.*;
class GFG {
 
  // Function to find whether an element is perfect square
  // or not
  static boolean checkperfectsquare(int x)
  {
 
    // If ceil and floor are equal the number is a
    // perfect square
    return Math.ceil(Math.sqrt(x))
      == Math.floor(Math.sqrt(x));
  }
 
  static int xorOfArray(int[] arr, int n)
  {
    // Stores final result
    int xor_arr = 0;
 
    // Iterating through every element in the array
    for (int i = 0; i < n; i++)
    {
 
      // Find XOR with the result
      if (checkperfectsquare(arr[i])) {
        xor_arr = xor_arr ^ arr[i];
      }
    }
 
    // Return the XOR
    return xor_arr;
  }
 
  public static void main(String[] args)
  {
    int[] arr = { 3, 9, 16, 12, 13, 15 };
    int N = arr.length;
 
    // Function call
    System.out.print(xorOfArray(arr, N));
  }
}
 
// This code is contributed by lokeshmvs21.

Python3

# Python3 program to find the XOR of
# all elements in the array
# which are perfect squares
 
import math
 
# Function to find whether
# an element is perfect square or not
def checkperfectsquare(x):
     
    # If ceil and floor are equal
    # the number is a perfect
    # square
    return math.ceil(math.sqrt(x)) == math.floor(math.sqrt(x))
 
def xorOfArray(arr, n):
     
    # Stores final result
    xor_arr = 0
     
    # Iterating through every element in
    # the array
    for i in range(n):
         
        # Find XOR with the result
        if checkperfectsquare(arr[i]):
            xor_arr = xor_arr ^ arr[i]
     
    # Return the XOR
    return xor_arr
 
# Driver Code
if __name__ == '__main__':
    arr = [3, 9, 16, 12, 13, 15]
    N = len(arr)
     
    # Function call
    print(xorOfArray(arr, N))

C#

// C# program to find the XOR of all elements in the array
// which are perfect squares
using System;
class GFG {
 
  // Function to find whether an element is perfect square
  // or not
  static Boolean checkperfectsquare(int x)
  {
 
    // If ceil and floor are equal the number is a
    // perfect square
    return Math.Ceiling(Math.Sqrt(x))
      == Math.Floor(Math.Sqrt(x));
  }
 
  static int xorOfArray(int[] arr, int n)
  {
    // Stores final result
    int xor_arr = 0;
 
    // Iterating through every element in the array
    for (int i = 0; i < n; i++)
    {
 
      // Find XOR with the result
      if (checkperfectsquare(arr[i])) {
        xor_arr = xor_arr ^ arr[i];
      }
    }
 
    // Return the XOR
    return xor_arr;
  }
 
  public static void Main()
  {
    int[] arr = { 3, 9, 16, 12, 13, 15 };
    int N = arr.Length;
 
    // Function call
    Console.Write(xorOfArray(arr, N));
  }
}
 
// This code is contributed by Saurabh Jaiswal

Javascript

       // JavaScript code for the above approach
 
       // Function to find whether
       // an element is perfect square or not
       function checkperfectsquare(x) {
 
           // If ceil and floor are equal
           // the number is a perfect
           // square
           return Math.ceil(Math.sqrt(x)) == Math.floor(Math.sqrt(x))
       }
       function xorOfArray(arr, n) {
 
           // Stores final result
           let xor_arr = 0
 
           // Iterating through every element in
           // the array
           for (let i = 0; i < n; i++) {
 
               // Find XOR with the result
               if (checkperfectsquare(arr[i])) {
                   xor_arr = xor_arr ^ arr[i]
               }
           }
           // Return the XOR
           return xor_arr
       }
        
       // Driver Code
       arr = [3, 9, 16, 12, 13, 15]
       N = arr.length
 
       // Function call
       console.log(xorOfArray(arr, N))
 
// This code is contributed by Potta Lokesh

Output

25

Time Complexity: O(Nlog(N))
Auxiliary Space: O(1)


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Sum of odd Array elements after each update query Sum of odd Array elements after each update query
Find minimum chocolates left after following the given rules Find minimum chocolates left after following the given rules
Why use an Array to implement a &quot;list&quot; instead of a Hash Table? Why use an Array to implement a &quot;list&quot; instead of a Hash Table?
Divide maximum element in N groups so that received and required has difference atmost K Divide maximum element in N groups so that received and required has difference atmost K
Minimum money required to buy items with given cashbacks Minimum money required to buy items with given cashbacks

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 14



 

Horje