Theprogrammersfirst | A technical portal.

The Fibonacci numbers are the numbers in the following integer sequence. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …….. In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation     Fn = Fn-1 + Fn-2 with seed values    F0 = 0 and F1 = 1. Given a number n, print n-th Fibonacci Number. Examples: Input  : n = 2 Output : 1 Input  : n = 9 Output : 34 Write a function int fib(int n) that returns Fn. For example, if n = 0, then fib() should return 0. If n = 1, then it should return 1. For n > 1, it should return Fn-1 + Fn-2 For n = 9 Output:34 Following are different methods to get the nth Fibonacci number. Method 1 ( Use recursion ) A simple method that is a direct recursive implementation mathematical recurrence relation given above. //Fibonacci Series using Recursion  class fibonacci  {      static int fib(int n)      {      if (n <= 1)      ...

Write an efficient program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum. kadane-algorithm Kadane’s Algorithm: Initialize:     max_so_far = 0     max_ending_here = 0 Loop for each element of the array   (a) max_ending_here = max_ending_here + a[i]   (b) if(max_so_far < max_ending_here)             max_so_far = max_ending_here   (c) if(max_ending_here < 0)             max_ending_here = 0 return max_so_far Explanation: Simple idea of the Kadane’s algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far     Lets take the example:     {-2, -3, 4...

Given an 2D array arr[][] consisting of N pairs of integers, the task is to find the pair which covers all other pairs of the given array. If it is impossible to find such a pair, then print -1. A pair {a,  b} will cover another pair {c,  d}, if the condition (a ≤ c ≤ d ≤ b) holds true. Examples: Input: arr[][2] = {{2, 2}, {3, 3}, {3, 5}, {4, 5}, {1, 1}, {1, 5}} Output: 6 Explanation: There exist a pair (1, 5) which cover all other pair because all other pair lies in the pair {1, 5}. Therefore, the position of the pair {1, 5} is 6. So, the output is 6. Input: arr[][] = {{1, 20}, {2, 22}, {3, 18}} Output: -1 Explanation: No such pair exists which covers all the remaining pairs. Therefore, the output is -1 Naive Approach: The simplest approach is to compare each pair with all other pairs and check if any pair covers all the pairs or not. Below are the steps: Initialize a variable count = 0 which stores the number pairs that lie between the current pair. Traverse the array of pairs and fo...

Given an array arr[] consisting of N positive integers and an integer K, which represents the maximum number that can be added to the array elements. The task is to maximize the length of longest possible subarray of equal elements by adding atmost K. Examples: Input: arr[] = {3, 0, 2, 2, 1}, k = 3 Output: 4 Explanation: Step 1: Adding 2 to arr[1] modifies array to {3, 2, 2, 2, 1} Step 2: Adding 1 to arr[4] modifies array to {3, 2, 2, 2, 2} Therefore, answer will be 4 ({arr[1], …, arr[4]}). Input: arr[] = {1, 1, 1}, k = 7 Output: 3 Explanation: All array elements are already equal. Therefore, the length is 3. Approach: Follow the steps below to solve the problem: Sort the array arr[]. Then, use Binary Search to pick a possible value for the maximum indices having the same element. For each picked_value, use the Sliding Window technique to check if it is possible to make all elements equal for any subarray of size picked_value. Finally, print the longest possible length of subarray obta...

Given an integer K and a numeric string str, the task is to find the longest subsequence from the given string which is divisible by K. Examples: Input: str = “121400”, K = 8 Output: 121400 Explanation: Since the whole string is divisible by 8, the entire string is the answer. Input: str: “7675437”, K = 64 Output: 64 Explanation: The longest subsequence from the string which is divisible by 64, is “64” itself. Approach: The idea is to find all subsequences of the given string and for each subsequence, check if its integer representation is divisible by K or not. Follow the steps below to solve the problem: Traverse the string. For every character encountered, two possibilities exists. Either consider the current character in the subsequence or not. For both the cases, proceed to the next characters of the string and find the longest subsequence that is divisible by K. Compare the longest subsequences obtained above with the current maximum length of longest subsequence and update accor...

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 integer N, the task is to find an integer K such that the sum of the numbers formed by repeated removal of last digit of K is equal to N. Examples: Input: N = 136 Output: 123 Explanation: Click to enlarge The numbers formed by repeatedly removing the last digit of 123 are {123, 12, 1}. Therefore, the sum of these numbers = 123 + 12 + 1 = 136( = N). Input: N = 107 Output: 98 Explanation: The numbers formed by repeatedly removing the last digit of 98 are {98, 9}. Therefore, the sum of these numbers = 98 + 7 = 107( = N). Approach: The approach is based on the following observations: Consider K = 123. The possible numbers formed from 123 are 1, 12, and 123. Now, 123 can be expressed as 100 + 20 + 3. If all the other numbers are expressed similarly, then the idea is to know the position and frequency of each digit in all the numbers combined, to get the total sum as N. Digit Frequency of each digit Sum units tens hundreds 1 1 1 1 1*1 + 1*10 + 1*100 = 111 2 1 1 ...

Given an array arr[] consisting of N integers, the task is to find all the array elements having frequency more than ⌊N/3⌋ in the given array. Examples: Input: arr[] = {5, 3, 5} Output: 5 Explanation: The frequency of 5 is 2, which is more than N/3( = 3/3 = 1). Input: arr[] = {7, 7, 7, 3, 4, 4, 4, 5} Output: 4 7 Explanation: The frequency of 7 and 4 in the array is 3, which is more than N/3( = 8/3 = 2). Approach: To solve the problem, the idea is to use Divide and Conquer technique. Follow the steps below to solve the problem: Initialize a function majorityElement() that will return the count of majority element in the array from any index left to right. Divide the given array arr[] into two halves and repeatedly pass it to the function majorityElement(). Initialize low and high as 0 and (N – 1) respectively. Compute the majority element using the following steps: If low = high: Return arr[low] as the majority element. Find the middle index,say mid(= (low + high)/2). Recursively call f...

Given an array arr[] consisting of N positive integers, the task is to find the sum of all array elements after reversing digits of every array element. Examples: Input: arr[] = {7, 234, 58100} Output: 18939 Explanation: Modified array after reversing each array elements = {7, 432, 18500}. Therefore, the sum of the modified array = 7 + 432 + 18500 = 18939. Input: arr[] = {0, 100, 220} Output: 320 Explanation: Modified array after reversing each array elements = {0, 100, 220}. Therefore, the sum of the modified array = 0 + 100 + 220 = 320. Approach: The idea is to reverse each number of the given array as per the given conditions and find sum of all array elements formed after reversing. Below steps to solve the problem: Initialize a variable, say sum, to store the required sum. Initialize variable count as 0 and f as false to store count of ending 0s of arr[i] and flag to avoid all non-ending 0. Initialize rev as 0 to store reversal of each array element. Traverse the given array and f...

Given two integers N and K, the task is to find the smallest number greater than N whose Kth bit in its binary representation is set. Examples: Input: N = 15, K = 2 Output: 20 Explanation: The binary representation of (20)10 is (10100)2. The 2nd bit(0-based indexing) from left is set in (20)10. Therefore, 20 is the smallest number greater than 15 having 2nd bit set. Input: N = 16, K = 3 Output: 24 Naive Approach: The simplest approach is to traverse all numbers starting from N + 1 and for each number, check if its Kth bit is set or not. If the such a number is found, then print that number. Below is the implementation of the above approach: // C++ program for the above approach     #include "bits/stdc++.h"  using namespace std;     // Function to find the number greater  // than n whose Kth bit is set  int find_next(int n, int k)  {      // Iterate from N + 1      int M = n + 1;       ...

Given an array arr[] consisting of N integers, the task is to check if it is possible to split the integers into two equal length subsets such that all repetitions of any array element belongs to the same subset. If found to be true, print “Yes”. Otherwise, print “No”. Examples: Input: arr[] = {2, 1, 2, 3} Output: Yes Explanation: One possible way of dividing the array is {1, 3} and {2, 2} Input: arr[] = {1, 1, 1, 1} Output: No Naive Approach: The simplest approach to solve the problem is to try all possible combinations of splitting the array into two equal subsets. For each combination, check whether every repetition belongs to only one of the two sets or not. If found to be true, then print “Yes”. Otherwise, print “No”. Time Complexity: O(2N), where N is the size of the given integer. Auxiliary Space: O(N) Efficient Approach: The above approach can be optimized by storing the frequency of all elements of the given array in an array freq[]. For elements to be divided into two equal s...

Given a 2D array Blocks[][] consisting of N rows of variable length. The task is to select at most M elements with maximum possible sum from Blocks[][] from either the start or end of a row. Examples: Input: N = 3, M = 4             Blocks[][] = {{2, 3, 5}, {-1, 7}, {8, 10}} Output: 30 Explanation: Select {5} from 1st row. Select {7} from 2nd row. Select {8, 10} from 3rd row. Input: N = 3, M = 2              Blocks[][] = {{100, 3, -1}, {-1, 7, 10}, {8, 10, 15}} Output: 115 Explanation:  select {100} from 1st row. Skip 2nd row. Select {15} from 3rd row. Naive Approach: The simplest approach is to iterate through all the rows of the matrix and push all the elements into a vector and sort it. Calculate the sum of last M elements and print it as the required answer. Time Complexity: O(N * KlogK), where K is the maximum size any block can have. Auxiliary Space: O(N * K) Efficient Approach : To optimize the above approach, ...