Quadruples for Sum and Product of Integers with XOR
Given an integer N, the task is to find X and Y where X is the number of quadruples of positive integers (A, B, C, D) such that AB + CD = N, Y is the number of quadruples of positive integers (A, B, C, D) such that (A + B)(C + D) = N. Print X XOR Y.
Examples:
Input: N = 4
Output: 9
Explanation: First we count X, the number of quadruples of positive integers (A, B, C, D) such that AB + CD = N
- (A, B, C, D) = (1, 1, 1, 3)
- (A, B, C, D) = (1, 1, 3, 1)
- (A, B, C, D) = (1, 2, 1, 2)
- (A, B, C, D) = (1, 2, 2, 1)
- (A, B, C, D) = (1, 3, 1, 1)
- (A, B, C, D) = (2, 1, 1, 2)
- (A, B, C, D) = (2, 1, 2, 1)
- (A, B, C, D) = (3, 1, 1, 1)
So, X = 8, Secondly we count Y, the number of quadruples of positive integers (A, B, C, D) such that (A + B)(C + D) = N
- (A, B, C, D) = (1, 1, 1, 1), So, Y = 1
Now, X XOR Y = 9
Input: N = 6
Output: 16
Approach: To solve the problem follow the below idea:
The main idea to solve the given problem is to find the number of quadruples of positive integers that satisfy the given equations, where X is the number of quadruples satisfying AB + CD = N, and Y is the number of quadruples satisfying (A + B)(C + D) = N. After finding X and Y, the XOR operation is performed between them to get the final result. This problem requires the use of mathematical techniques to derive formulas for X and Y, followed by their computation using a suitable algorithm.
Below are the steps for the above approach:
- Create a function countDivisors(int n) that counts the number of divisors of n.
- Initialize a variable cnt = 0.
- Iterate from i = 1 to sqrt(n).
- Check if n is divisible by i, then check if n/i == i, increment cnt by 1, else increment count by 2.
- Return cnt.
- Create a function counttuples(int n) that counts the total number of quadruples of positive integers (A, B, C, D) such that AB + CD = N.
- Initialize a variable cnt = 0.
- Iterate from i = 2 to n-1.
- Check if n is divisible by i, initialize two temporary variables temp1 = i-1 and temp2 = (n / i) – 1
- Add temp1 * temp2 to cnt.
- Return cnt.
- Initialize two variables X and Y to zero.
- Iterate from i = 1 to n-1.
- Calculate the number of divisors ‘a’ of i using the countDivisors(i) function.
- Calculate the number of divisors ‘b’ of (n – i) using the countDivisors(n – i) function.
- Add a * b to X.
- Find the number of quadruples Y of positive integers (A, B, C, D) such that (A + B)(C + D) = N using counttuples(n) function.
- Print (X XOR Y).
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to count the divisors int countDivisors( int n) { int cnt = 0; for ( int i = 1; i * i <= n; i++) { if (n % i == 0) { // If divisors are equal, // count only one if (n / i == i) cnt++; // Otherwise count both else cnt = cnt + 2; } } return cnt; } // Function to find the total number of // quadruples of positive integers // (A, B, C, D) such that (A + B)(C + D) = N int counttuples( int n) { int cnt = 0; // Run a for loop 2 to n-1, because // 1*n = n but we cannot write 1 as // the addition of two positive integer, // so we cancel this two factor for ( int i = 2; i < n; i++) { // Now we check if a number from 2 // to n-1 is a factor of n, or not if (n % i == 0) { // We write a number as the // addition of two number // n-1 times int temp1 = i - 1; int temp2 = (n / i) - 1; cnt += (temp1 * temp2); } } return cnt; } // Driver Code int main() { int n = 6; int X = 0; for ( int i = 1; i < n; i++) { int a = countDivisors(i); int b = countDivisors(n - i); X += (a * b); } int Y = counttuples(n); cout << (X ^ Y) << endl; return 0; } |
Java
import java.util.*; public class Main { // Function to count the divisors static int countDivisors( int n) { int cnt = 0 ; for ( int i = 1 ; i * i <= n; i++) { if (n % i == 0 ) { // If divisors are equal, // count only one if (n / i == i) cnt++; // Otherwise count both else cnt += 2 ; } } return cnt; } // Function to find the total number of // quadruples of positive integers // (A, B, C, D) such that (A + B)(C + D) = N static int counttuples( int n) { int cnt = 0 ; // Run a for loop 2 to n-1, because // 1*n = n but we cannot write 1 as // the addition of two positive integer, // so we cancel this two factor for ( int i = 2 ; i < n; i++) { // Now we check if a number from 2 // to n-1 is a factor of n, or not if (n % i == 0 ) { // We write a number as the // addition of two number // n-1 times int temp1 = i - 1 ; int temp2 = (n / i) - 1 ; cnt += (temp1 * temp2); } } return cnt; } // Driver Code public static void main(String[] args) { int n = 6 ; int X = 0 ; for ( int i = 1 ; i < n; i++) { int a = countDivisors(i); int b = countDivisors(n - i); X += (a * b); } int Y = counttuples(n); System.out.println(X ^ Y); } } // This code is contributed by Prajwal Kandekar |
Python3
import math # Function to count the divisors def countDivisors(n): cnt = 0 for i in range ( 1 , int (math.sqrt(n)) + 1 ): if n % i = = 0 : # If divisors are equal, # count only one if n / i = = i: cnt + = 1 # Otherwise count both else : cnt + = 2 return cnt # Function to find the total number of # quadruples of positive integers # (A, B, C, D) such that (A + B)(C + D) = N def counttuples(n): cnt = 0 # Run a for loop 2 to n-1, because # 1*n = n but we cannot write 1 as # the addition of two positive integer, # so we cancel this two factor for i in range ( 2 , n): # Now we check if a number from 2 # to n-1 is a factor of n, or not if n % i = = 0 : # We write a number as the # addition of two number # n-1 times temp1 = i - 1 temp2 = (n / / i) - 1 cnt + = (temp1 * temp2) return cnt # Driver Code if __name__ = = '__main__' : n = 6 X = 0 for i in range ( 1 , n): a = countDivisors(i) b = countDivisors(n - i) X + = (a * b) Y = counttuples(n) print (X ^ Y) |
C#
using System; using System.Collections.Generic; public class MainClass { // Function to count the divisors static int countDivisors( int n) { int cnt = 0; for ( int i = 1; i * i <= n; i++) { if (n % i == 0) { // If divisors are equal, // count only one if (n / i == i) cnt++; // Otherwise count both else cnt += 2; } } return cnt; } // Function to find the total number of // quadruples of positive integers // (A, B, C, D) such that (A + B)(C + D) = N static int counttuples( int n) { int cnt = 0; // Run a for loop 2 to n-1, because // 1*n = n but we cannot write 1 as // the addition of two positive integer, // so we cancel this two factor for ( int i = 2; i < n; i++) { // Now we check if a number from 2 // to n-1 is a factor of n, or not if (n % i == 0) { // We write a number as the // addition of two number // n-1 times int temp1 = i - 1; int temp2 = (n / i) - 1; cnt += (temp1 * temp2); } } return cnt; } // Driver Code public static void Main( string [] args) { int n = 6; int X = 0; for ( int i = 1; i < n; i++) { int a = countDivisors(i); int b = countDivisors(n - i); X += (a * b); } int Y = counttuples(n); Console.WriteLine(X ^ Y); } } |
Javascript
// Function to count the divisors function countDivisors(n) { let cnt = 0; for (let i = 1; i <= Math.floor(Math.sqrt(n)); i++) { if (n % i === 0) { // If divisors are equal, count only one if (n / i === i) { cnt += 1; } // Otherwise count both else { cnt += 2; } } } return cnt; } // Function to find the total number of // quadruples of positive integers // (A, B, C, D) such that (A + B)(C + D) = N function counttuples(n) { let cnt = 0; // Run a for loop 2 to n-1, because // 1*n = n but we cannot write 1 as // the addition of two positive integer, // so we cancel this two factor for (let i = 2; i < n; i++) { // Now we check if a number from 2 // to n-1 is a factor of n, or not if (n % i === 0) { // We write a number as the // addition of two number // n-1 times let temp1 = i - 1; let temp2 = Math.floor(n / i) - 1; cnt += temp1 * temp2; } } return cnt; } // Driver Code let n = 6; let X = 0; for (let i = 1; i < n; i++) { let a = countDivisors(i); let b = countDivisors(n - i); X += a * b; } let Y = counttuples(n); console.log(X ^ Y); |
16
Time Complexity: O(n^(3/2))
Auxiliary Space: O(1)
Contact Us