Given an array arr[] and an integer x, the task is to check whether the sum of all the perfect squares from the array is divisible by x or not. If divisible then print Yes else print No.
Examples:
Input: arr[] = {2, 3, 4, 6, 9, 10}, x = 13
Output: Yes
4 and 9 are the only perfect squares from the array
sum = 4 + 9 = 13 (which is divisible by 13)Input: arr[] = {2, 4, 25, 49, 3, 8}, x = 9
Output: No
Approach: Run a loop from i to n – 1 and check whether arr[i] is a perfect square or not. If arr[i] is a perfect square then update sum = sum + arr[i]. If in the end sum % x = 0 then print Yes else print No. To check whether an element is a perfect square or not, follow the following steps:
Let num be an integer element
float sq = sqrt(x)
if floor(sq) = ceil(sq) then num is a perfect square else not.
Algorithm:
Step 1: Start
Step 2: Create a function called “check” that accepts the arguments “arr,” “x,” and “n” as an array of integers.
Step 3: Create the long variable “sum” and set its initial value to 0.
Step 4: From 0 to n-1 times, iterate, and for each index i.
a. Calculate arr[isquare ]’s root and place the result in the double variable “sqrt.”
b. Include arr[i] in the sum if sqrt is an integer.
Step 5: Return true if the total of all perfect squares in arr can be divided by x; otherwise, return false.
Step 6: End
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function that returns true if the sum of all the// perfect squares of the given array are divisible by xbool check(int arr[], int x, int n){ long long sum = 0; for (int i = 0; i < n; i++) { double x = sqrt(arr[i]); // If arr[i] is a perfect square if (floor(x) == ceil(x)) { sum += arr[i]; } } if (sum % x == 0) return true; else return false;}// Driver codeint main(){ int arr[] = { 2, 3, 4, 9, 10 }; int n = sizeof(arr) / sizeof(arr[0]); int x = 13; if (check(arr, x, n)) { cout << "Yes"; } else { cout << "No"; } return 0;} |
Java
// Java implementation of the approach public class GFG{ // Function that returns true if the sum of all the // perfect squares of the given array is divisible by x static boolean check(int arr[], int x, int n) { long sum = 0; for (int i = 0; i < n; i++) { double y = Math.sqrt(arr[i]); // If arr[i] is a perfect square if (Math.floor(y) == Math.ceil(y)) { sum += arr[i]; } } if (sum % x == 0) return true; else return false; } // Driver Code public static void main(String []args){ int arr[] = { 2, 3, 4, 9, 10 }; int n = arr.length ; int x = 13; if (check(arr, x, n)) { System.out.println("Yes"); } else { System.out.println("No"); } } // This code is contributed by Ryuga} |
Python3
# Python3 implementation of the approachimport math# Function that returns true if the sum of all the # perfect squares of the given array is divisible by xdef check (a, y): sum = 0 for i in range(len(a)): x = math.sqrt(a[i]) # If a[i] is a perfect square if (math.floor(x) == math.ceil(x)): sum = sum + a[i] if (sum % y == 0): return True else: return False # Driver codea = [2, 3, 4, 9, 10]x = 13if check(a, x) : print("Yes")else: print("No") |
C#
// C# implementation of the approach using System;public class GFG{ // Function that returns true if the sum of all the // perfect squares of the given array is divisible by x static bool check(int[] arr, int x, int n) { long sum = 0; for (int i = 0; i < n; i++) { double y = Math.Sqrt(arr[i]); // If arr[i] is a perfect square if (Math.Floor(y) == Math.Ceiling(y)) { sum += arr[i]; } } if (sum % x == 0) return true; else return false; } // Driver Code public static void Main(){ int[] arr = { 2, 3, 4, 9, 10 }; int n = arr.Length ; int x = 13; if (check(arr, x, n)) { Console.Write("Yes"); } else { Console.Write("No"); } } } |
PHP
<?php// PHP implementation of the approach// Function that returns true if the // sum of all the perfect squares of // the given array is divisible by xfunction check($arr, $x, $n){ $sum = 0; for ($i = 0; $i < $n; $i++) { $x = sqrt($arr[$i]); // If arr[i] is a perfect square if (floor($x) == ceil($x)) { $sum += $arr[$i]; } } if (($sum % $x) == 0) return true; else return false;}// Driver code$arr = array( 2, 3, 4, 9, 10 );$n = sizeof($arr);$x = 13;if (!check($arr, $x, $n)) { echo "Yes";}else{ echo "No";}// This code is contributed by Sachin?> |
Javascript
<script>// Javascript implementation of the approach // Function that returns true if the sum of all the // perfect squares of the given array is divisible by x function check(arr,x,n) { let sum = 0; for (let i = 0; i < n; i++) { let y = Math.sqrt(arr[i]); // If arr[i] is a perfect square if (Math.floor(y) == Math.ceil(y)) { sum += arr[i]; } } if (sum % x == 0) return true; else return false; } // Driver Code let arr=[ 2, 3, 4, 9, 10]; let n = arr.length ; let x = 13; if (check(arr, x, n)) { document.write("Yes"); } else { document.write("No"); } // This code is contributed by unknown2108 </script> |
Yes
Complexity Analysis:
- Time Complexity: O(nlogn)
- Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
