More Useful Applications - Prefix Sum Array

PHOTO EMBED

Mon Feb 07 2022 16:14:27 GMT+0000 (UTC)

Saved by @Uttam #java #gfg #geeksforgeeks #arrays #prefixsum #subarrays #moreproblems

1.) Maximum subarray size, such that all subarrays of that size have sum less than k: 
-------------------------------------------------------------------------------------
    Given an array of n positive integers and a positive integer k, the task is to find the maximum 	subarray size such that all subarrays of that size have the sum of elements less than k.

    https://www.geeksforgeeks.org/maximum-subarray-size-subarrays-size-sum-less-k/

2.) Find the prime numbers which can written as sum of most consecutive primes: 
-------------------------------------------------------------------------------
    Given an array of limits. For every limit, find the prime number which can be written as the 	 sum of the most consecutive primes smaller than or equal to the limit.
    
    https://www.geeksforgeeks.org/find-prime-number-can-written-sum-consecutive-primes/

3.) Longest Span with same Sum in two Binary arrays : 
-----------------------------------------------------
    Given two binary arrays, arr1[] and arr2[] of the same size n. Find the length of the longest       common span (i, j) where j >= i such that arr1[i] + arr1[i+1] + …. + arr1[j] = arr2[i] +           arr2[i+1] + …. + arr2[j].
    
    https://www.geeksforgeeks.org/longest-span-sum-two-binary-arrays/

3.) Maximum subarray sum modulo m: 
----------------------------------
    Given an array of n elements and an integer m. The task is to find the maximum value of the sum 	of its subarray modulo m i.e find the sum of each subarray mod m and print the maximum value of 	this modulo operation.
    
    https://www.geeksforgeeks.org/maximum-subarray-sum-modulo-m/

4.) Maximum subarray size, such that all subarrays of that size have sum less than k: 
-------------------------------------------------------------------------------------
	Given an array of n positive integers and a positive integer k, the task is to find the maximum 	subarray size such that all subarrays of that size have sum of elements less than k.
    
    https://www.geeksforgeeks.org/maximum-subarray-size-subarrays-size-sum-less-k/

5.) Minimum cost for acquiring all coins with k extra coins allowed with every coin: 
---------------------------------------------------------------------------------
	You are given a list of N coins of different denominations. you can pay an amount equivalent to 	any 1 coin and can acquire that coin. In addition, once you have paid for a coin, we can choose 	at most K more coins and can acquire those for free. The task is to find the minimum amount 	required to acquire all the N coins for a given value of K.

    https://www.geeksforgeeks.org/minimum-cost-for-acquiring-all-coins-with-k-extra-coins-allowed-with-every-coin/
    
6.) Random number generator in arbitrary probability distribution fashion: 
----------------------------------------------------------------------
	Given n numbers, each with some frequency of occurrence. Return a random number with a 			probability proportional to its frequency of occurrence.
    
    https://www.geeksforgeeks.org/random-number-generator-in-arbitrary-probability-distribution-fashion/
content_copyCOPY