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 = 25Input: 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.
- For each element in the array, check if it is a perfect square or not.
- 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 |
25
Time Complexity: O(Nlog(N))
Auxiliary Space: O(1)