Count elements in an Array that can be represented as difference of two perfect squares
Given an array arr[], the task is to count the number of elements in the array that can be represented as in the form of the difference of two perfect square numbers.
Examples:
Input: arr[] = {1, 2, 3}
Output: 2
Explanation:
There are two such elements that can be represented as
difference of square of two numbers –
Element 1 –
Element 3 –
Therefore, Count of such elements is 2.
Input: arr[] = {2, 5, 6}
Output: 1
Explanation:
There is only one such element. That is –
Element 5 –
Therefore, Count of such elements is 1.
Approach: The key observation in the problem is numbers which can be represented as the difference of the squares of two numbers never yield 2 as the remainder when divided by 4.
For Example:
N = 4 =>
N = 6 => Can’t be represented as
N = 8 =>
N = 10 => Can’t be represented as
Therefore, iterate over the array and count the number of such elements in the array.
Below is the implementation of the above approach:
C++
// C++ implementation to count the // number of elements which can be // represented as the difference // of the two square #include <bits/stdc++.h> using namespace std; // Function to count of such elements // in the array which can be represented // as the difference of the two squares int count_num( int arr[], int n) { // Initialize count int count = 0; // Loop to iterate // over the array for ( int i = 0; i < n; i++) // Condition to check if the // number can be represented // as the difference of squares if ((arr[i] % 4) != 2) count++; cout << count; return 0; } // Driver code int main() { int arr[] = { 1, 2, 3 }; int n = sizeof (arr) / sizeof (arr[0]); count_num(arr, n); return 0; } |
Java
// Java implementation to count the // number of elements which can be // represented as the difference // of the two square class GFG{ // Function to count of such elements // in the array which can be represented // as the difference of the two squares static void count_num( int []arr, int n) { // Initialize count int count = 0 ; // Loop to iterate // over the array for ( int i = 0 ; i < n; i++) { // Condition to check if the // number can be represented // as the difference of squares if ((arr[i] % 4 ) != 2 ) count++; } System.out.println(count); } // Driver code public static void main (String[] args) { int arr[] = { 1 , 2 , 3 }; int n = arr.length; count_num(arr, n); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 implementation to count the # number of elements in the array # which can be represented as difference # of the two elements # Function to return the # Count of required count # of such elements def count_num(arr, n): # Initialize count count = 0 # Loop to iterate over the # array of elements for i in arr: # Condition to check if the # number can be represented # as the difference # of two squares if ((i % 4 ) ! = 2 ): count = count + 1 return count # Driver Code if __name__ = = "__main__" : arr = [ 1 , 2 , 3 ] n = len (arr) # Function Call print (count_num(arr, n)) |
C#
// C# implementation to count the // number of elements which can be // represented as the difference // of the two square using System; class GFG{ // Function to count of such elements // in the array which can be represented // as the difference of the two squares static void count_num( int []arr, int n) { // Initialize count int count = 0; // Loop to iterate // over the array for ( int i = 0; i < n; i++) { // Condition to check if the // number can be represented // as the difference of squares if ((arr[i] % 4) != 2) count++; } Console.WriteLine(count); } // Driver code public static void Main( string [] args) { int []arr = { 1, 2, 3 }; int n = arr.Length; count_num(arr, n); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // Javascript implementation to count the // number of elements which can be // represented as the difference // of the two square // Function to count of such elements // in the array which can be represented // as the difference of the two squares function count_num(arr, n) { // Initialize count let count = 0; // Loop to iterate // over the array for (let i = 0; i < n; i++) // Condition to check if the // number can be represented // as the difference of squares if ((arr[i] % 4) != 2) count++; document.write(count); return 0; } let arr = [ 1, 2, 3 ]; let n = arr.length; count_num(arr, n); </script> |
Output:
2
Time complexity: O(n) where n is the number of elements in the given array
Auxiliary space: O(1)
Contact Us