Theprogrammersfirst | A technical portal.

Given an integer K and an array arr[] consisting of N positive integers, the task is to find the number of subarrays whose sum modulo K is equal to the size of the subarray. Examples: Input: arr[] = {1, 4, 3, 2}, K = 3 Output: 4 Explanation: 1 % 3 = 1 (1 + 4) % 3 = 2 4 % 3 = 1 (3 + 2) % 3 = 2 Therefore, subarrays {1}, {1, 4}, {4}, {3, 2} satisfy the required conditions. Input: arr[] = {2, 3, 5, 3, 1, 5}, K = 4 Output: 5 Explanation: The subarrays (5), (1), (5), (1, 5), (3, 5, 3) satisfy the required condition. Naive Approach: The simplest approach is to find the prefix sum of the given array, then generate all the subarrays of the prefix sum array and count those subarrays having sum modulo K equal to the length of that subarray. Print the final count of subarrays obtained. Below is the implementation of the above approach: // C++ program of the above approach     #include <bits/stdc++.h>  using namespace std;     // Function that counts the suba...

Given an array arr[] consisting of N integers, the task is to create an array brr[] of size N where brr[i] represents the count of subarrays in which arr[i] is the smallest element. Examples: Input: arr[] = {3, 2, 4}  Output: {1, 3, 1}  Explanation:  For arr[0], there is only one subarray in which 3 is the smallest({3}).  For arr[1], there are three such subarrays where 2 is the smallest({2}, {3, 2}, {2, 4}).  For arr[2], there is only one subarray in which 4 is the smallest({4}). Input: arr[] = {1, 2, 3, 4, 5}  Output: {5, 4, 3, 2, 1} Recommended: Please try your approach on {IDE} first, before moving on to the solution. Naive Approach: The simplest approach is to generate all subarrays of the given array and for every array element arr[i], count the number of subarrays in which it is the smallest element.  Time Complexity: O(2N)  Auxiliary Space: O(N) Efficient Approach: To optimize the above approach, the idea is to find the boundary index for ...

it is a software development technique that imposes a hierarchical structure on the design of the program. It starts out by defining the solution at the highest level of functionality and breaking it down further and further into small routines that can be easily documented and coded.  Also called " stepwise refinement". structured programming Techniques that impose a logical structure to the coding of a program in order to make it easy to follow. Large routines are broken down into small modules that have to be methodically and carefully nested within each other, because the use of the GOTO statement is either discouraged or not available in the language. Structured walkthroughs, which invite criticism from peer programmers, are also used. Structured languages, such as Pascal, Ada and dBASE, force the programmer to write a structured program; however, all programming languages can be written in a structured manner.