HackerRank: Find Maximum Index Product ( Stack, DS ) (Find me on HackerRank @ Handle: BishalG ) Problem Summary: According to problem, you are given an array A of length n . For each index - i in the array, calculate IndexProduct(i) which is defined as: IndexProduct(i) = Left(i) * Right(i). Again, Left(i) and Right(i) has following definition: Left(i) = Index on the left side of the array such that j < i and arr[j] > arr[i] Right(i) = Index on the right side of the array such that j > i and arr[j] > arr[i] If such index does not exist then it would be 0 in both cases. Our task is to find maximum of IndexProduct(i) among all values of i. Solution Idea: I'm explaining here the idea for generating values for Left array. Similar concept can be applied to find the values for Right array. After finding both arrays, we can easily calculate IndexProduct for every i and find the maximum value among them which will be our answer. Calculating Left array: If we think ...
Sample Problem: Electronics Shop ( HackerRank ) (Find me on HackerRank @ Handle: BishalG ) Problem Summary: In this problem, you are given two arrays of positive integer numbers of lengths n and m respectively and another positive integer b . Your task is to find out the maximum integer formed by the summation of two integer values taken from different arrays and is less than or equal to b. If there does not exist such summation print -1 . Solution Idea: Since the constraints for n and m are small ( i.e. 1 <= n, m <= 1000 ) , so this problem is very much suitable to test different variants of our solution approaches. Here, we will discuss about 3 different approaches to solve this problem progressively starting from least efficient solution to most efficient one. Approach - 1: Brute-force If we think in brute-force manner, the naive approach to solve this problem will be to try every possible pairing among these two arrays. For this, we can just it...
HDU - 4734 : F(X) [Digit DP] IDEA : Problem is asking for how many integers( x ) are there in the range 0 to B, which have F( x ) less than or equal to F(A). Simply a digit dp with state "POS" , "If we take any less digit" and "Tot sum for F(x)" . But, the main problem is that there are lot of test cases..So, to avoid clearing DP array for each testcases, we only memorize two state POS & SUM, so that we have only one state which will be not memorized in each testcases. CODE : ///==================================================/// /// HELLO WORLD !! /// /// IT'S ME /// /// BISHAL GAUTAM /// /// [ bsal.gautam16@gmail.com ] /// ///==================================================/// #include<bits / stdc + + .h> #define X first #define Y second #define mpp make_pair #define nl printf( " \n ...
Comments
Post a Comment