0

Finding Sum

Finding Sum Problem Description You are given a set of N positive integers and another integer P, where P is a small prime. You need to write a program to count the number of subsets of size (cardinality) 3, the sum of whose elements is divisible by P. Since the number K of such sets can be huge, output K modulo 10007 1009 (the remainder when K is divided by 1009) Constraints N <= 500 P<50 All integers <=1000 Input Format First line two comma separated integers N, P The next line contains N comma separated integers Output One integer giving the number of subsets the sum of whose elements is divisible by P. Give result modulo 1009 Explanation Example 1 Input 4,5 5,10,15,20 Output 4 Explanation Every non empty subset of the given numbers has sum of its elements a multiple of 5. Since there are 4 subsets of size 3, the output is 4. Example 2 Input 5,5 3,7,12,13,15 Output 4 Explanation There are 4 subsets of size 3 with sum a multiple of 5: {3, 7, 15}, {12, 13, 15}, {7, 13, 15}, {3, 12, 15}, Hence the output is 4.

21st Jul 2018, 4:45 AM
ravindra reddy
ravindra reddy - avatar
7 Answers
0
only for some test cases #include<stdio.h> int main(){ int n,i,j,k,sum=0,a[100],p,c=0; scanf("%d,%d\n",&n,&p); for(i=0;i<n;i++) { scanf("%d,",&a[i]); } for (i = 0; i < n; i++) { for (j = i + 1; j < n;) { if (a[j] == a[i]) { for (k = j; k < n; k++) { a[k] = a[k + 1]; } n--; } else j++; } } for(i=0;i<n;i++) { for(j=i+1;j<n;j++) { for(k=j+1;k<n;k++) { sum=a[i]+a[j]+a[k]; if(sum%p==0) c++; sum=0; } } } printf("%d",c); return 0; }
21st Jul 2018, 6:13 AM
Merla Hari
Merla Hari - avatar
0
import java.util.Scanner; public class MyClass { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String input = sc.next(); String ans[] = input.split(","); int n = Integer.parseInt(ans[0]); int p = Integer.parseInt(ans[1]); int arr[] = new int[n]; String arrin = sc.next(); String an[] = arrin.split(","); for (int i = 0; i < n; i++) { arr[i] = Integer.parseInt(an[i]); if(arr[i]>1000) return; } int cnt = 0; if(n>500 || p>49) return; else{ for (int i = 0; i < arr.length - 2; i++) { for (int j = 1; j < arr.length - 1; j++) { for (int k = 2; k < arr.length; k++) { if ((arr[i] + arr[j] + arr[k]) % p == 0 && (i != j) && (j != k) && (i != k)) { cnt++; //System.out.println(arr[i] + " " + arr[j] + " " + arr[k]); } } } } System.out.println(cnt%1009); } } }
21st Jul 2018, 7:53 AM
Mukund Singh
Mukund Singh - avatar
0
#include<stdio.h> int main(){ int n,i,j,k,sum=0,a[100],p,c=0; scanf("%d,%d\n",&n,&p); for(i=0;i<n;i++) { scanf("%d,",&a[i]); } for (i = 0; i < n; i++) { for (j = i + 1; j < n;) { if (a[j] == a[i]) { for (k = j; k < n; k++) { a[k] = a[k + 1]; } n--; } else j++; } } for(i=0;i<n;i++) { for(j=i+1;j<n;j++) { for(k=j+1;k<n;k++) { sum=a[i]+a[j]+a[k]; if(sum%p==0) c++; sum=0; } } } printf("%d",c); return 0; }
21st Jul 2018, 8:18 AM
jyoti patel
jyoti patel - avatar
0
import java.util.Scanner; public class MyClass { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String input = sc.next(); String ans[] = input.split(","); int n = Integer.parseInt(ans[0]); int p = Integer.parseInt(ans[1]); int arr[] = new int[n]; String arrin = sc.next(); String an[] = arrin.split(","); if(an.length != n) return; for (int i = 0; i < n; i++) { arr[i] = Integer.parseInt(an[i]); if(arr[i]>1000) return; } int cnt = 0; boolean pIsprime = true; int c=2; while(pIsprime && c<=p/2){ if(p%c == 0) pIsprime = false; c++; } if(n>500 || p>49 || n<0 || !pIsprime || p<2) return; else{ for (int i = 0; i < arr.length - 2; i++) { for (int j = 1; j < arr.length - 1; j++) { for (int k = 2; k < arr.length; k++) { if ((arr[i] + arr[j] + arr[k]) % p == 0 && (i != j) && (j != k) && (i != k)) { cnt++; //System.out.println(arr[i] + " " + arr[j] + " " + arr[k]); } } } } System.out.println(cnt%1009); } } }
21st Jul 2018, 8:21 AM
Mukund Singh
Mukund Singh - avatar
0
It works can you show me the error.
21st Jul 2018, 4:51 PM
Mukund Singh
Mukund Singh - avatar
- 1
This code not working Help me to solve
21st Jul 2018, 12:17 PM
Karan
Karan - avatar
- 1
Write a C program to sum first 100, 500 and then 1000 terms of sum Sk N=∑ 1 N 1/i k . It should take k and N as input and give the sum as output. Plot the output with respect to i=1:N. For k=2, draw a horizontal line at y=(∏^2)/6 . Do similar plots for k=4, 6, 8. 10.
22nd Aug 2020, 10:25 AM
Uday Teja
Uday Teja - avatar