Given N numbers, find the number of permutations in which the sum of elements at odd index and sum of elements at even index are equal.
Examples:
Input: 1 2 3 Output: 2 The permutations are: 1 3 2 sum at odd index = 1+2 = 3, sum at even index = 3 2 3 1 sum at odd index = 2+1 = 3, sum at even index = 3 Input: 1 2 1 2 Output: 3 The permutations are: 1 2 2 1 2 1 1 2 2 2 1 1
The approach to the problem will be to use next_permutation() in C++ STL which helps to generate all the possible permutation of N numbers. If the sum of the odd index elements is equal to the sum of even index elements of the generated permutation, then increase the count. When all permutations are checked, print the count.
Below is the implementation of the above approach:
C++
// C++ program to find number of permutations// such that sum of elements at odd index // and even index are equal#include <bits/stdc++.h>using namespace std;// Function that returns the number of permutationsint numberOfPermutations(int a[], int n){ int sumEven, sumOdd, c = 0; // iterate for all permutations do { // stores the sum of odd and even index elements sumEven = sumOdd = 0; // iterate for elements in permutation for (int i = 0; i < n; i++) { // if odd index if (i % 2) sumOdd += a[i]; else sumEven += a[i]; } // If condition holds if (sumOdd == sumEven) c++; } while (next_permutation(a, a + n)); // return the number of permutations return c;}// Driver Codeint main(){ int a[] = { 1, 2, 3 }; int n = sizeof(a) / sizeof(a[0]); // Calling Function cout << numberOfPermutations(a, n); return 0;} |
Java
// Java program to find number of permutations // such that sum of elements at odd index // and even index are equal class GFG {// Function that returns the number of permutations static int numberOfPermutations(int a[], int n) { int sumEven, sumOdd, c = 0; // iterate for all permutations do { // stores the sum of odd and even index elements sumEven = sumOdd = 0; // iterate for elements in permutation for (int i = 0; i < n; i++) { // if odd index if (i % 2 == 0) { sumOdd += a[i]; } else { sumEven += a[i]; } } // If condition holds if (sumOdd == sumEven) { c++; } } while (next_permutation(a)); // return the number of permutations return c; } static boolean next_permutation(int[] p) { for (int a = p.length - 2; a >= 0; --a) { if (p[a] < p[a + 1]) { for (int b = p.length - 1;; --b) { if (p[b] > p[a]) { int t = p[a]; p[a] = p[b]; p[b] = t; for (++a, b = p.length - 1; a < b; ++a, --b) { t = p[a]; p[a] = p[b]; p[b] = t; } return true; } } } } return false; }// Driver Code public static void main(String args[]) { int a[] = {1, 2, 3}; int n = a.length; System.out.println(numberOfPermutations(a, n)); }}/*This code is contributed by 29AjayKumar*/ |
Python3
# Python3 program to find number of permutations# such that sum of elements at odd index # and even index are equaldef next_permutation(arr): arrCount = len(arr); # the head of the suffix i = arrCount - 1; # find longest suffix while (i > 0 and arr[i] <= arr[i - 1]): i-=1; # are we at the last permutation already? if (i <= 0): return [False,arr]; # get the pivot pivotIndex = i - 1; # find rightmost element that exceeds the pivot j = arrCount - 1; while (arr[j] <= arr[pivotIndex]): j-=1; # swap the pivot with j temp = arr[pivotIndex]; arr[pivotIndex] = arr[j]; arr[j] = temp; # reverse the suffix j = arrCount - 1; while (i < j): temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i+=1; j-=1; return [True,arr];# Function that returns the number # of permutationsdef numberOfPermutations(a, n): sumEven=0; sumOdd=0; c = 0; # iterate for all permutations while (True): # stores the sum of odd and # even index elements sumEven = 0; sumOdd = 0; # iterate for elements in permutation for i in range(n): # if odd index if (i % 2): sumOdd += a[i]; else: sumEven += a[i]; # If condition holds if (sumOdd == sumEven): c+=1; xx=next_permutation(a); if(xx[0]==False): break; a=xx[1]; # return the number of permutations return c;# Driver Codea = [1, 2, 3];n = len(a);# Calling Functionprint(numberOfPermutations(a, n));# This code is contributed by mits |
C#
// C# program to find number of permutations // such that sum of elements at odd index // and even index are equal using System; public class GFG { // Function that returns the number of permutations static int numberOfPermutations(int []a, int n) { int sumEven, sumOdd, c = 0; // iterate for all permutations do { // stores the sum of odd and even index elements sumEven = sumOdd = 0; // iterate for elements in permutation for (int i = 0; i < n; i++) { // if odd index if (i % 2 == 0) { sumOdd += a[i]; } else { sumEven += a[i]; } } // If condition holds if (sumOdd == sumEven) { c++; } } while (next_permutation(a)); // return the number of permutations return c; } static bool next_permutation(int[] p) { for (int a = p.Length - 2; a >= 0; --a) { if (p[a] < p[a + 1]) { for (int b = p.Length - 1;; --b) { if (p[b] > p[a]) { int t = p[a]; p[a] = p[b]; p[b] = t; for (++a, b = p.Length - 1; a < b; ++a, --b) { t = p[a]; p[a] = p[b]; p[b] = t; } return true; } } } } return false; }// Driver Code public static void Main() { int []a = {1, 2, 3}; int n = a.Length; Console.WriteLine(numberOfPermutations(a, n)); }}/*This code is contributed by 29AjayKumar*/ |
PHP
<?php// PHP program to find number of permutations// such that sum of elements at odd index // and even index are equalfunction next_permutation(&$input){ $inputCount = count($input); // the head of the suffix $i = $inputCount - 1; // find longest suffix while ($i > 0 && $input[$i] <= $input[$i - 1]) { $i--; } // are we at the last permutation already? if ($i <= 0) { return false; } // get the pivot $pivotIndex = $i - 1; // find rightmost element that exceeds the pivot $j = $inputCount - 1; while ($input[$j] <= $input[$pivotIndex]) { $j--; } // swap the pivot with j $temp = $input[$pivotIndex]; $input[$pivotIndex] = $input[$j]; $input[$j] = $temp; // reverse the suffix $j = $inputCount - 1; while ($i < $j) { $temp = $input[$i]; $input[$i] = $input[$j]; $input[$j] = $temp; $i++; $j--; } return true;}// Function that returns the number // of permutationsfunction numberOfPermutations($a, $n){ $sumEven; $sumOdd; $c = 0; // iterate for all permutations do { // stores the sum of odd and // even index elements $sumEven = $sumOdd = 0; // iterate for elements in permutation for ($i = 0; $i < $n; $i++) { // if odd index if ($i % 2) $sumOdd += $a[$i]; else $sumEven += $a[$i]; } // If condition holds if ($sumOdd == $sumEven) $c++; } while (next_permutation($a)); // return the number of permutations return $c;}// Driver Code$a = array(1, 2, 3);$n = count($a);// Calling Functionecho numberOfPermutations($a, $n);// This code is contributed by// Rajput-Ji?> |
Javascript
<script>// javascript program to find number of permutations // such that sum of elements at odd index // and even index are equal // Function that returns the number of permutations function numberOfPermutations( a , n) { var sumEven, sumOdd, c = 0; // iterate for all permutations do { // stores the sum of odd and even index elements sumEven = sumOdd = 0; // iterate for elements in permutation for (var i = 0; i < n; i++) { // if odd index if (i % 2 == 0) { sumOdd += a[i]; } else { sumEven += a[i]; } } // If condition holds if (sumOdd == sumEven) { c++; } } while (next_permutation(a)); // return the number of permutations return c; } function next_permutation(p) { for (var a = p.length - 2; a >= 0; --a) { if (p[a] < p[a + 1]) { for (var b = p.length - 1;; --b) { if (p[b] > p[a]) { var t = p[a]; p[a] = p[b]; p[b] = t; for (++a, b = p.length - 1; a < b; ++a, --b) { t = p[a]; p[a] = p[b]; p[b] = t; } return true; } } } } return false; } // Driver Code var a = [ 1, 2, 3 ]; var n = a.length; document.write(numberOfPermutations(a, n));// This code contributed by Princi Singh</script> |
Output
2
Time Complexity: O(N! * N)
Auxiliary Space: O(1) because it is using constant space for variables
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!
