Given a number N. Find the number of ways to divide a number into four parts(a, b, c, d) such that a = c and b = d and a not equal to b.
Examples:
Input : N = 6
Output : 1
Explanation : four parts are {1, 2, 1, 2}
Input : N = 20
Output : 4
Explanation : possible ways are {1, 1, 9, 9}, {2, 2, 8, 8}, {3, 3, 7, 7} and {4, 4, 6, 6}.
Naive Approach
The idea is to run four nested loops from 1 to N and pick four numbers such that their sum is equal to N and the first number=third number and the second number=fourth number and the first number!=second number. Every time you pick any numbers then count that. Now those numbers will be repeated means the value in the first, third number and second,fourth number will be interchanged and it will be counted.
For example if N=6 then 1,2,1,2 and 2,1,2,1 both will be counted. So final answer will be the counted answer by 2.
Steps to implement-
- Initialize a variable count with 0. This will contain the final answer
- After that run four nested loops from 1 to n
- When all the values give the sum to n and the value from the first loop is equal to the value from the third loop and the value from the second loop is equal to the value from the fourth loop and the value from the first loop is not equal to the value from the second loop then increment the count
- Then print or return count/2
Code-
C++
// C++ implementation for above approach#include <bits/stdc++.h>using namespace std;// Function to find the number of ways to divide// N into four parts such that a = c and b = dint possibleways(int n){ int count=0; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ for(int p=1;p<=n;p++){ for(int q=1;q<=n;q++){ //When all four numbers satisfy given condition then increment the count if((i+j+p+q==n) && (i==p) && (j==q) && (i!=j)){ count++;} } } } } //return count/2 because one set of numbers will be counted twice return count/2;}// Driver codeint main(){ int n = 20; cout << possibleways(n); return 0;} |
Java
// Java implementation for above approachimport java.util.*;class Main { // Function to find the number of ways // to divide N into four parts such // that a = c and b = d public static int possibleWays(int n) { int count = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int p = 1; p <= n; p++) { for (int q = 1; q <= n; q++) { // When all four numbers // satisfy given condition // then increment count if ((i + j + p + q == n) && (i == p) && (j == q) && (i != j)) { count++; } } } } } // return count / 2 because one set of // numbers will be counted twice return count / 2; } // Driver Code public static void main(String[] args) { int n = 20; System.out.println(possibleWays(n)); }} |
Python3
def possibleways(n): count = 0 for i in range(1, n+1): for j in range(1, n+1): for p in range(1, n+1): for q in range(1, n+1): # When all four numbers satisfy the given condition, # increment the count if (i + j + p + q == n) and (i == p) and (j == q) and (i != j): count += 1 # Return count // 2 because one set of numbers will be counted twice return count // 2# Driver coden = 20print(possibleways(n)) |
C#
// C# implementation for above approachusing System;class MainClass {// Function to find the number of ways to divide// N into four parts such that a = c and b = dstatic int PossibleWays(int n) {int count = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {for (int p = 1; p <= n; p++) {for (int q = 1; q <= n; q++) {// When all four numbers satisfy given condition then increment the countif ((i+j+p+q == n) && (i == p) && (j == q) && (i != j)) {count++;}}}}}// Return count/2 because one set of numbers will be counted twicereturn count/2;}// Main functionstatic void Main() {int n = 20;Console.WriteLine(PossibleWays(n));}} |
Javascript
// Function to find the number of ways to // divide N into four parts such that a = c and b = dfunction possibleways(n) { let count = 0; for (let i = 1; i <= n; i++) { for (let j = 1; j <= n; j++) { for (let p = 1; p <= n; p++) { for (let q = 1; q <= n; q++) { // When all four numbers satisfy given condition then // increment the count if ((i + j + p + q == n) && (i == p) && (j == q) && (i != j)) { count++; } } } } } // return count/2 because one set of numbers will be counted twice return count / 2;}// Driver codelet n = 20;console.log(possibleways(n)); |
Output
4
Time Complexity: O(N4), because of 4 nested loops from 1 to N
Auxiliary Space: O(1), because no extra space has been used
Approach :
If the given N is odd the answer is 0, because the sum of four parts will not be even number.
If n is divisible by 4 then answer will be n/4 -1(here a equals to b can be possible so subtract that possibility) otherwise n/4.
Below is the implementation of the above approach :
C++
// C++ implementation for above approach#include <bits/stdc++.h>using namespace std;// Function to find the number of ways to divide// N into four parts such that a = c and b = dint possibleways(int n){ if (n % 2 == 1) return 0; else if (n % 4 == 0) return n / 4 - 1; else return n / 4;}// Driver codeint main(){ int n = 20; cout << possibleways(n); return 0;} |
Java
// Java implementation for above approachclass GFG{ // Function to find the number of ways to divide// N into four parts such that a = c and b = dstatic int possibleways(int n){ if (n % 2 == 1) return 0; else if (n % 4 == 0) return n / 4 - 1; else return n / 4;}// Driver codepublic static void main(String[] args){ int n = 20; System.out.println(possibleways(n));}}// This code contributed by Rajput-Ji |
Python3
# Python3 implementation for above approach# Function to find the number of ways # to divide N into four parts # such that a = c and b = ddef possibleways(n): if (n % 2 == 1): return 0; elif (n % 4 == 0): return n // 4 - 1; else: return n // 4;# Driver coden = 20;print(possibleways(n));# This code is contributed by mits |
C#
// C# implementation for above approachclass GFG{ // Function to find the number of ways to divide// N into four parts such that a = c and b = dstatic int possibleways(int n){ if (n % 2 == 1) return 0; else if (n % 4 == 0) return n / 4 - 1; else return n / 4;}// Driver codestatic void Main(){ int n = 20; System.Console.WriteLine(possibleways(n));}}// This code is contributed by mits |
Javascript
<script>// java script implementation for above approach// Function to find the number of ways to divide// N into four parts such that a = c and b = dfunction possibleways(n){ if (n % 2 == 1) return 0; else if (n % 4 == 0) return n / 4 - 1; else return n / 4;}// Driver codelet n = 20;document.write( possibleways(n));// This code is contributed by Gottumukkala Bobby</script> |
PHP
<?php// PHP implementation for above approach// Function to find the number of ways to divide// N into four parts such that a = c and b = dfunction possibleways($n){ if ($n % 2 == 1) return 0; else if ($n % 4 == 0) return $n / 4 - 1; else return $n / 4;}// Driver code$n = 20;echo possibleways($n);// This code is contributed by ajit?> |
Output
4
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
