Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

HackerRank Wet Shark and Two Subsequences problem solution

YASH PAL, 31 July 2024

In this HackerRank Wet Shark and Two Subsequences problem solution we have given an array X and we need to find all pairs of subsequences (A, B) and we need to determine how many possible subsequences A and B can exist.

hackerrank wet shark and two subsequences problem solution

Problem solution in Python.

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'twoSubsequences' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER_ARRAY x
#  2. INTEGER r
#  3. INTEGER s
#
mod = 10**9+7
def twoSubsequences(x, r, s):
    # Write your code here
    if r<s or (r+s)%2==1 or r==0:
        return 0
    h,l = (r+s)//2, (r-s)//2
    m = len(x)
    dp = [[0 for i in range(m+1)] for j in range(h+1)]
    dp[0][0] = 1
    if x[0]<=h:
        dp[x[0]][1] = 1
    for i in range(1, m):
        for j in range(h,0,-1):
            for k in range(1,m+1):
                if j>=x[i]:
                    dp[j][k] = (dp[j][k]+dp[j-x[i]][k-1]) % mod
    res = 0
    for k in range(1,m+1):
        res  = (res+dp[h][k]*dp[l][k]) % mod
    return res
        
            

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()

    m = int(first_multiple_input[0])

    r = int(first_multiple_input[1])

    s = int(first_multiple_input[2])

    x = list(map(int, input().rstrip().split()))

    result = twoSubsequences(x, r, s)

    fptr.write(str(result) + 'n')

    fptr.close()

{“mode”:”full”,”isActive”:false}

Problem solution in Java.

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

    /*
     * Complete the twoSubsequences function below.
     */
    static int twoSubsequences(int[] X, int r, int s) {
        /*
         * Write your code here.
         */
        final long MOD=1000000007;
        int n = (r + s) / 2, l = (r - s) / 2,m=X.length;
        long result=0;
        long[][] dp=new long[n + 1][m + 1];
        dp[0][0] = 1;
    if(X[0] <= n) {
        dp[X[0]][1] = 1;
    }
    for(int i = 1; i < m; i++) {
        dp[0][0] = 1;
        for(int k = 1; k <= m; k++) {
            dp[0][k] = 0;
        }
        for(int j = n; j >= 1; j--) {
            dp[j][0] = 0;
            for(int k = 1; k <= m; k++) {
                if(j < X[i]) {
                    dp[j][k] = dp[j][k];
                } else {
                    dp[j][k] = (dp[j - X[i]][k - 1] + dp[j][k]) % MOD;
                }
            }
        }
    }
    if(l >= 0 && (r + s) % 2 != 1 && (r - s) % 2 != 1 && r != 0) {
        for(int i = 0; i <= m; i++) {
            result = (result + dp[n][i] * dp[l][i]) % MOD;
        }
    }
    return (int)result;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] mrs = scanner.nextLine().split(" ");

        int m = Integer.parseInt(mrs[0].trim());

        int r = Integer.parseInt(mrs[1].trim());

        int s = Integer.parseInt(mrs[2].trim());

        int[] x = new int[m];

        String[] xItems = scanner.nextLine().split(" ");

        for (int xItr = 0; xItr < m; xItr++) {
            int xItem = Integer.parseInt(xItems[xItr].trim());
            x[xItr] = xItem;
        }

        int result = twoSubsequences(x, r, s);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedWriter.close();
    }
}

{“mode”:”full”,”isActive”:false}

Problem solution in C++.

#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define VAR(v, i) __typeof(i) v=(i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(v) (v).begin(),(v).end()

#define VI vector<int>
#define PII pair<int,int>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define lint long long int

#define debug(x) {cerr <<#x <<" = " <<x <<endl; }
#define debug2(x,y) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y <<endl; } 
#define debug3(x,y,z) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y << ", " << #z << " = " << z <<endl; } 
#define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<endl; }}
#define debugt(t,n) {{cerr <<#t <<" = "; FOR(it,0,(n)) cerr <<t[it] <<", "; cerr <<endl; }}

#define make( x) int (x); scanf("%d",&(x));
#define make2( x, y) int (x), (y); scanf("%d%d",&(x),&(y));
#define make3(x, y, z) int (x), (y), (z); scanf("%d%d%d",&(x),&(y),&(z));
#define make4(x, y, z, t) int (x), (y), (z), (t); scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define makev(v,n) VI (v); FOR(i,0,(n)) { make(a); (v).pb(a);} 
#define IOS ios_base::sync_with_stdio(0)
#define HEAP priority_queue

#define read( x) scanf("%d",&(x));
#define read2( x, y) scanf("%d%d",&(x),&(y));
#define read3(x, y, z) scanf("%d%d%d",&(x),&(y),&(z));
#define read4(x, y, z, t) scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define readv(v,n) FOR(i,0,(n)) { make(a); (v).pb(a);}

using namespace std;
#define max_n 100005

int mod = 1e9+7;
int dp[2005][105];
int dp2[2005][105];

int main(){
	make3(m,r,s);
	if((r+s)%2!=0){
		makev(v,m);
		printf("0n");
	}
	else{
		makev(v,m);
		int sum = (r+s)/2, diff = (r-s)/2;
		if(diff < 0){
			printf("0n");
			return 0;
		}
		FOR(i,0,sum+1) FOR(j,0,m+1) dp[i][j] = 0;
		dp[0][0] = 1;

		FOR(i,0,m){
			FOR(j,0,sum+1){
				FOR(k,0,m+1){
					dp2[j][k] = dp[j][k] + ((j>=v[i] && k > 0) ? dp[j-v[i]][k-1] : 0);
					dp2[j][k] %= mod;
				}
			}
			FOR(q,0,sum+1) FOR(j,0,m+1)  dp[q][j] = dp2[q][j];
		}
		int ans = 0;
		FOR(i,1,m+1){
			ans += (dp[sum][i]*1LL*dp[diff][i])%mod;
			ans %= mod;
		}
		printf("%dn",ans);
	}
}


{“mode”:”full”,”isActive”:false}

Problem solution in C.

#include "stdio.h"
#include "string.h"

int dp[4010][102];
int a[102];
const int MOD = (1e9) + 7;

int main() {
    int m, r, s;
    while (scanf("%d%d%d",&m,&r,&s) != EOF) {
        for (int i = 0 ; i < m ; ++i)
            scanf("%d", &a[i]);
        if (r == 0 && s == 0) {
            printf("0n");
            continue;
        }
        if ((r + s) % 2 == 1 || r < s) {
            printf("0n");
            continue;
        }

        int maxS = (r + s + 1) / 2;
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for (int i = 0 ; i < m ; ++i) {
            for (int sum = maxS ; sum >= 0 ; --sum) {
                if (sum + a[i] > maxS) continue;
                for (int cnt = 0 ; cnt <= i ; ++cnt) {
                    dp[sum+a[i]][cnt+1] += dp[sum][cnt];
                    dp[sum+a[i]][cnt+1] %= MOD;
                }
            }
        }
        int total = 0;
        for (int cnt = 0 ; cnt <= m ; ++cnt) {
            total += (int)((long long)dp[(r+s)/2][cnt] * dp[(r-s)/2][cnt] % MOD);
            total %= MOD;
        }
        printf("%dn",total);
    }
    return 0;
}

{“mode”:”full”,”isActive”:false}

Algorithms coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes