Ron Wesley has been bit by a three headed snake and Harry Potter is searching for a potion. The Witch promises to tell the ingredients of the medicine if Harry can find equi pair of an array. Listen to the conversation between Harry The witch to know more about equi pairs.
Conversation:
The Witch: To find the equi pair, you must know how to find the slices first.
Harry: What is a slice?
The Witch: If Z is an array with N elements, a slice of indices (X, Y) is Z[X] + Z[X+1]…Z[Y]
Harry: How can I use it to find equi pair?
The Witch: (a, b) is an equi pair if slice of (0, a-1) = slice of (a+1, b-1) = slice of (b+1, N-1) and b>a+1 and size of array > 4
Input Format:
An array of N integers delimited by white space.
Output Format:
Print equi pair in first line in the format {a,b }
Print slices in the format {0, a-1}, { a+1,b-1 }, { b+1,N-1 }
OR
Print “Array does not contain any equi pair” if there are no equi pairs in the array.
Constraints:
Zi >= 0 and 1<= i <=N
size of array (N) > 4
b > (a+1)
Example 1
Input:
8 3 5 2 10 6 7 9 5 2
Output:
Indices which form equi pair {3, 6}
Slices are { 0,2 },{ 4,5 },{ 7,9 }
Example 2
Input:
6 2 6 2 3 3 1 9
Output:
Array does not contain any equi pair.
Solution: In C
#include<stdio.h>
#define For(i,n) for(i=0;i<n;i++)
#define FOR(i,n) for(i=n-1;i>=0;i--)
#define nl printf("\n")
int main()
{
int a[100005],ind=0,i,n;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&a[i]);
}
int k,j,fl=0;
For(i,n){
if(i==0){}
else a[i]+=a[i-1];
}
for(i=0;i<n;i++){
for(j=i+2;j<n-2;j++){
if(a[i]==a[j]-a[i+1] && a[j]-a[i+1]==a[n-1]-a[j+1]){
printf("Indices which form equi pair { %d,%d }\n",i+1,j+1);
printf("Slices are { 0,%d },{ %d,%d },{ %d,%d }\n",i,i+2,j,j+2,n-1);
fl=1;
}
}
}
if(fl==0){
printf("Array does not contain any equi pair\n");
}
return 0;
}Solution: In Java
import java.util.*;
class Main{
public static void main(String[] args){
Scanner ip=new Scanner(System.in);
int[] a=new int[100];
int i,n;
n=ip.nextInt();
for(i=0;i<n;i++){
a[i]=ip.nextInt();
}
int k,j,fl=0;
for(i=0;i<n;i++){
if(i==0){}
else a[i]+=a[i-1];
}
for(i=0;i<n;i++){
for(j=i+2;j<n-2;j++){
if(a[i]==a[j]-a[i+1] && a[j]-a[i+1]==a[n-1]-a[j+1]){
System.out.printf("Indices which form equi pair {%d,%d}\n",i+1,j+1);
System.out.printf("Slices are {0,%d },{%d,%d },{%d,%d}\n",i,i+2,j,j+2,n-1);
fl=1;
}
}
}
if(fl==0){
System.out.printf("Array does not contain any equi pair\n");
}
}
}Solution: In Python 3
n = int(input())
a = list(map(int,input().split()))
def check_eqipair(i,j):
if sum(a[:i]) == sum(a[i+1:j]) == sum(a[j+1:n]):
return 1
return 0
for i in range(1,n-1):
for j in range(i+1,n):
x = check_eqipair(i,j)
if x == 1:
break
if x == 1:
break
if x == 0:
print('Array does not contain any equi pair')
else:
print("Indices which form equi pair {%d,%d}"%(i,j))
print("Slices are {%d,%d},{%d,%d},{%d,%d}"%(0,i-1,i+1,j-1,j+1,n-1))Also Checkout