Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programming101

Learn everything about programming

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}

algorithm coding problems

Post navigation

Previous post
Next post
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
  • Hackerrank Day 14 scope 30 days of code solution
©2025 Programming101 | WordPress Theme by SuperbThemes