HackerRank Candles Counting Problem Solution Yashwant Parihar, August 7, 2023August 1, 2024 In this post, we will solve HackerRank Candles Counting Problem Solution. Tim is visiting his grandma for two days and is bored due to the lack of the electricity over there. That’s why he starts to play with grandma’s colorful candle collection.He aligned the N candles from left to right. The ith candle from the left has the height H and the color C₂, an integer ranged from 1 to a given K. the number of colors.Now he stares at the sequence of candles and wonders, how many strictly increasing (in height) colorful subsequences are there? A subsequence is considered as colorful if every of the K colors appears at least one times in the subsequence.As the number of subsequences fulfilling the requirement can be large, print the result modulo 10 power 9 +7.Input FormatOn the first line you will be given N and K. then N lines will follow. On the ith line you will be given two integers H, and C. Output Format Print the number of strictly increasing colorful subsequences modulo 10 power 9 +7. Sample Input 4 3 1 1 3 2 2 2 4 3 Sample Output 2 Explanation In the first sample the only two valid subsequences are (1, 2, 4) and (1, 3, 4). HackerRank Candles Counting Problem Solution Candles Counting C Solution #include <assert.h> #include <limits.h> #include <math.h> #include <stdbool.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #define MOD 1000000007 #define HEIGHT 50001 #define LNHT 16 char* readline(); char** split_string(char*); /* * Complete the candlesCounting function below. */ int candlesCounting(int k, int n, int** candles) { int *seqsegtree[1<<k][LNHT + 1]; for(int i = 0; i < 1<<k; i++){ for(int j = 0; j <= LNHT; j++){ seqsegtree[i][j] = malloc(sizeof(int)<<(LNHT - j)); for(int a = 0; a < 1<<(LNHT - j); a++){ seqsegtree[i][j][a] = 0; } } } for(int j = 0; j <= LNHT; j++){ seqsegtree[0][j][0] = 1; } for(int i = 0; i < n; i++){ int ht = candles[i][0]; int color = candles[i][1] - 1; for(int dig = LNHT; dig >= 0; dig--){ if(((ht>>dig)&1) == 1){ for(int j = 0; j < 1<<k; j++){ seqsegtree[j | 1<<color][0][ht] = (seqsegtree[j | 1<<color][0][ht] + seqsegtree[j][dig][(ht>>dig) - 1])%MOD; } } } for(int dig = 0; dig < LNHT; dig++){ int nextpos = ht>>(dig + 1); for(int j = 0; j < 1<<k; j++){ seqsegtree[j][dig + 1][nextpos] = (seqsegtree[j][dig][2*nextpos] + seqsegtree[j][dig][2*nextpos + 1])%MOD; } } } return seqsegtree[(1<<k) - 1][LNHT][0]; } int main() { FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w"); char** nk = split_string(readline()); char* n_endptr; char* n_str = nk[0]; int n = strtol(n_str, &n_endptr, 10); if (n_endptr == n_str || *n_endptr != '\0') { exit(EXIT_FAILURE); } char* k_endptr; char* k_str = nk[1]; int k = strtol(k_str, &k_endptr, 10); if (k_endptr == k_str || *k_endptr != '\0') { exit(EXIT_FAILURE); } int** candles = malloc(n * sizeof(int*)); for (int candles_row_itr = 0; candles_row_itr < n; candles_row_itr++) { *(candles + candles_row_itr) = malloc(2 * (sizeof(int))); char** candles_item_temp = split_string(readline()); for (int candles_column_itr = 0; candles_column_itr < 2; candles_column_itr++) { char* candles_item_endptr; char* candles_item_str = *(candles_item_temp + candles_column_itr); int candles_item = strtol(candles_item_str, &candles_item_endptr, 10); if (candles_item_endptr == candles_item_str || *candles_item_endptr != '\0') { exit(EXIT_FAILURE); } *(*(candles + candles_row_itr) + candles_column_itr) = candles_item; } } int result = candlesCounting(k, n, candles); fprintf(fptr, "%d\n", result); fclose(fptr); return 0; } char* readline() { size_t alloc_length = 1024; size_t data_length = 0; char* data = malloc(alloc_length); while (true) { char* cursor = data + data_length; char* line = fgets(cursor, alloc_length - data_length, stdin); if (!line) { break; } data_length += strlen(cursor); if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; } size_t new_length = alloc_length << 1; data = realloc(data, new_length); if (!data) { break; } alloc_length = new_length; } if (data[data_length - 1] == '\n') { data[data_length - 1] = '\0'; } data = realloc(data, data_length); return data; } char** split_string(char* str) { char** splits = NULL; char* token = strtok(str, " "); int spaces = 0; while (token) { splits = realloc(splits, sizeof(char*) * ++spaces); if (!splits) { return splits; } splits[spaces - 1] = token; token = strtok(NULL, " "); } return splits; } Candles Counting C++ Solution #include <algorithm> #include <cstdio> #include <iostream> using namespace std; const int MAXK = 15; const int MAXN = 5e4+54; const long long int MOD = 1e9+7; struct Candle{ int height, colour, index; Candle( int height_=0, int colour_=0, int index_=0 ){ height = height_; colour = colour_; index = index_; } friend bool operator < ( const Candle &a, const Candle &b ){ if( a.height == b.height ) return a.index > b.index; return a.height < b.height; } }; struct Fenwick{ int N; long long int *bit; void init( int N_ ){ N = N_; bit = new long long int[N+1]; } void add( int index, long long int value ){ for( int i=index ; i<=N ; i += i&-i ) bit[i] = (bit[i] + value) % MOD; } long long int sum( int l, int r ){ if( l > r ) return 0; long long int rev = 0LL; for( int i=r ; i ; i -= i&-i ) rev = (rev + bit[i]) % MOD; for( int i=l-1 ; i ; i -= i&-i ) rev = (rev - bit[i] + MOD) % MOD; return rev; } ~Fenwick(){ delete [] bit; } }; int N, K; Candle ar[MAXN]; Fenwick dn[1 << MAXK]; int main(){ scanf("%d%d", &N, &K); for( int i=0 ; i < (1 << K) ; i++ ) dn[i].init(N); for( int i=1 ; i<=N ; i++ ){ scanf("%d%d", &ar[i].height, &ar[i].colour); ar[i].colour--; ar[i].index = i; } sort(ar+1, ar+N+1); for( int i=N ; i ; i-- ){ for( int mask = 0 ; mask < (1 << K) ; mask++ ) dn[mask | (1 << ar[i].colour)].add(ar[i].index, dn[mask].sum(ar[i].index+1, N)); dn[1 << ar[i].colour].add(ar[i].index, 1LL); } printf("%lld\n", dn[(1 << K) - 1].sum(1, N)); return 0; } Candles Counting C Sharp Solution using System.CodeDom.Compiler; using System.Collections.Generic; using System.Collections; using System.ComponentModel; using System.Diagnostics.CodeAnalysis; using System.Globalization; using System.IO; using System.Linq; using System.Reflection; using System.Runtime.Serialization; using System.Text.RegularExpressions; using System.Text; using System; class Result { /* * Complete the 'candlesCounting' function below. * * The function is expected to return an INTEGER. * The function accepts following parameters: * 1. INTEGER k * 2. 2D_INTEGER_ARRAY candles */ private static long Mod = 1000000007; public class Candles { public long[] array; public Candles(int size) { array = new long[size +1]; } public long cal(int idx) { long sum = 0; while (idx > 0) { sum += array[idx]; idx -= idx & -idx; } return sum % Mod; } public void update(int idx, long value) { while (idx < array.Length) { array[idx] = (array[idx] + value) % Mod; idx += idx & -idx; } } } public static int candlesCounting(int k, List<List<int>> candles) { int maxHeight = candles.Max(q => q[0]); int n = candles.Count; int per = (int)Math.Pow(2, k); Candles[] dp = new Candles[per]; for (int tree = 0; tree < per; tree++) { dp[tree] = new Candles(maxHeight + 2); } dp[0].update(1, 1); for (int i = 0; i < n; i++) { int height = candles[i][0]+1; int color = candles[i][1] - 1; for (int j = 1; j < per; j++) { if ((j & (1 << color)) != 0) { int newcol = (j & ((1 << color) - 1)) | (j & ((~((1 << color) - 1)) << 1)); long count = (dp[newcol].cal(height - 1) + dp[j].cal(height - 1)) % Mod; if (count > 0) { dp[j].update(height, count); } } } } return (int)dp[per - 1].cal(maxHeight + 1); } } class Solution { public static void Main(string[] args) { TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true); string[] firstMultipleInput = Console.ReadLine().TrimEnd().Split(' '); int n = Convert.ToInt32(firstMultipleInput[0]); int k = Convert.ToInt32(firstMultipleInput[1]); List<List<int>> candles = new List<List<int>>(); for (int i = 0; i < n; i++) { candles.Add(Console.ReadLine().TrimEnd().Split(' ').ToList().Select(candlesTemp => Convert.ToInt32(candlesTemp)).ToList()); } int result = Result.candlesCounting(k, candles); textWriter.WriteLine(result); textWriter.Flush(); textWriter.Close(); } } Candles Counting Java Solution import java.util.Scanner; public class HackerRankCandleCountingFenwick { private static final Scanner scanner = new Scanner(System.in); private static final long PLONG = (long) Math.pow(10, 9) + 7; private static final int PINT = (int) Math.pow(10, 9) + 7; public static class FenwickCandles { private final int[] array; public FenwickCandles(int size) { array = new int[size + 1]; } public int treeSum() { return sumUpToIdx(this.size() - 1); } public int sumUpToIdx(int idx) { idx++; // translate from 0-indexed input to 1-indexed array assert idx > 0; long sum = 0; while (idx > 0) { sum += array[idx]; idx -= idx & (-idx); } return (int) (sum % PLONG); } public void update(int idx, int value) { idx++; // translate from 0-indexed input to 1-indexed array assert idx > 0; while (idx < array.length) { array[idx] = (array[idx] + value) % PINT; idx += idx & (-idx); } } public int size() { return array.length - 1; } } static int candlesCounting(int k, int n, int[][] candles, int maxHeight) { int bLen = (int) Math.pow(2, k); FenwickCandles[] allBSTs = new FenwickCandles[bLen]; int[] newCount = new int[bLen]; for (int tree = 1; tree < bLen; tree++) { allBSTs[tree] = new FenwickCandles(maxHeight + 1); } for (int i = 0; i < n; i++) { int height = candles[i][0]; int candleColor = candles[i][1] - 1; newCount[1 << candleColor] = 1; for (int tree = 1; tree < bLen; tree++) { int count = allBSTs[tree].sumUpToIdx(height - 1); if (count > 0) { // nth bit represents color n int newJ = tree | (1 << candleColor); newCount[newJ] = (newCount[newJ] + count) % PINT; } if (newCount[tree] > 0) { allBSTs[tree].update(height, newCount[tree]); newCount[tree] = 0; } } } return allBSTs[bLen - 1].treeSum(); } public static void main(String[] args) { String[] nk = scanner.nextLine().split(" "); int n = Integer.parseInt(nk[0]); int k = Integer.parseInt(nk[1]); int[][] candles = new int[n][2]; int maxH = 0; for (int row = 0; row < n; row++) { String[] s = scanner.nextLine().split(" "); for (int col = 0; col < 2; col++) { int i = Integer.parseInt(s[col]); if (col == 0 && i > maxH) { maxH = i; } candles[row][col] = i; } } int result = candlesCounting(k, n, candles, maxH); System.out.println(result); scanner.close(); } } Candles Counting JavaScript Solution const fs = require("fs"); // Read all lines from STDIN const buffer = fs.readFileSync(0); const lines = buffer.toString().split("\n"); // Used for parsing each line const parse = (line) => line.trim().split(" ").map(Number); const MOD = 10 ** 9 + 7; // Binary Indexed Tree for representing an array A of size n class BIT { constructor(n) { this.nodes = new Array(n + 1).fill(0); } get size() { return this.nodes.length; } // Get sum of elements of A in range [0, index] query(index) { let sum = 0; for (; index > 0; index -= index & -index) { sum += this.nodes[index]; } return sum; } // Update BIT when 'value' is added to A[index] update(index, value) { for (; index < this.size; index += index & -index) { this.nodes[index] += value; this.nodes[index] %= MOD; } } } const [n, k] = parse(lines[0]); const H = []; const C = []; for (let i = 1; i <= n; i++) { const [h, c] = parse(lines[i]); H.push(h); C.push(c); } let count = 0; // Maximum size of BIT const max = Math.max(...H); // colors is a k-bit mask where the i-th bit is set if a color i is to be included in the subsequence for (let colors = 1; colors < 1 << k; colors++) { /* A BIT for representing an imaginary 1-indexed array A, where A[value] contains the number of subsequences ending with 'value' */ const bit = new BIT(max); for (let i = 0; i < n; i++) { // Consider candle i only if its color is included in the mask 'colors' if ((colors >> (C[i] - 1)) & 1) { // Number of subsequences ending with A[[H[i]]] = 1 + Sum of number of subsequences ending with [1,2,3,..., H[i] - 1] // Update the BIT since A[[H[i]]] is updated. bit.update(H[i], 1 + bit.query(H[i] - 1)); } } // Find number of increasing subsequences that contain candles of any number of colors if (colors.toString(2).match(/1/g).length % 2 == k % 2) { count += bit.query(bit.size - 1); count %= MOD; } else { // Remove the increasing subsequences that do not contain candles of k colors count -= bit.query(bit.size - 1); count %= MOD; } } console.log(count); Candles Counting Python Solution #!/bin/python import math import os import random import re import sys # # Complete the 'candlesCounting' function below. # # The function is expected to return an INTEGER. # The function accepts following parameters: # 1. INTEGER k # 2. 2D_INTEGER_ARRAY candles # MOD = pow(10, 9) + 7 def update(bit, index, delta): while index < len(bit): bit[index] = (bit[index] + delta) % MOD index += index & (-index) def query(bit, index): range_sum = 0 while index > 0: range_sum = (range_sum + bit[index]) % MOD index -= index & (-index) return range_sum def candlesCounting(k, candles): heights = sorted([candle[0] for candle in candles]) ranks = {} for index, height in enumerate(heights): ranks[height] = index + 1 for candle_index in range(len(candles)): candles[candle_index][0] = ranks[candles[candle_index][0]] max_color = max(candle[1] for candle in candles) color_states = 1 << max_color dp = [[0] * (len(candles) + 1) for _ in range(color_states)] for candle_index in range(len(candles)): height_rank = candles[candle_index][0] curr_color_state = 1 << (candles[candle_index][1] - 1) for color_state in range(color_states): if ((color_state & curr_color_state) == 0): continue curr_color_bit_removed_state = color_state ^ curr_color_state curr_color_bit_removed_count = query(dp[curr_color_bit_removed_state], height_rank - 1) color_state_count = query(dp[color_state], height_rank - 1) if color_state == curr_color_state: color_state_count += 1 update(dp[color_state], height_rank, curr_color_bit_removed_count + color_state_count) return query(dp[-1], len(candles)) if __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w') first_multiple_input = raw_input().rstrip().split() n = int(first_multiple_input[0]) k = int(first_multiple_input[1]) candles = [] for _ in xrange(n): candles.append(map(int, raw_input().rstrip().split())) result = candlesCounting(k, candles) fptr.write(str(result) + '\n') fptr.close() c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython