• Skip to primary navigation
  • Skip to main content
  • Skip to primary sidebar

Pro Programming

Professional way of Programming: Learn C, C++, Java, Python, Dot Net, Android the professional way

  • Home
  • C MCQs
  • C/C++ Programs
  • Java Programs
  • C#
  • Python
  • MySQL
  • Topics
    • Arrays
    • Strings
    • Link Lists
    • Trees
    • Shapes
  • Projects
  • Articles
  • Games
You are here: Home / Archives for Longest subsequence such that adjacent elements have at least one common digit

Longest subsequence such that adjacent elements have at least one common digit

Count pairs of non-overlapping palindromic sub-strings of the given string

Leave a Comment


#include <bits/stdc++.h>

using namespace std;

#define N 100

  

void pre_process(bool dp[N][N], string s)

{

  

    

    int n = s.size();

  

    

    

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < n; j++)

            dp[i][j] = false;

    }

  

    

    for (int j = 1; j <= n; j++) {

  

        

        

        for (int i = 0; i <= n - j; i++) {

  

            

            if (j <= 2) {

  

                

                if (s[i] == s[i + j - 1])

                    dp[i][i + j - 1] = true;

            }

  

            

            else if (s[i] == s[i + j - 1])

                dp[i][i + j - 1] = dp[i + 1][i + j - 2];

        }

    }

}

  

int countPairs(string s)

{

  

    

    bool dp[N][N];

    pre_process(dp, s);

    int n = s.length();

  

    

    int left[n];

    memset(left, 0, sizeof left);

  

    

    int right[n];

    memset(right, 0, sizeof right);

  

    

    left[0] = 1;

  

    

    

    for (int i = 1; i < n; i++) {

  

        for (int j = 0; j <= i; j++) {

  

            if (dp[j][i] == 1)

                left[i]++;

        }

    }

  

    

    right[n - 1] = 1;

  

    

    

    for (int i = n - 2; i >= 0; i--) {

  

        right[i] = right[i + 1];

  

        for (int j = n - 1; j >= i; j--) {

  

            if (dp[i][j] == 1)

                right[i]++;

        }

    }

  

    int ans = 0;

  

    

    for (int i = 0; i < n - 1; i++)

        ans += left[i] * right[i + 1];

  

    return ans;

}

  

int main()

{

    string s = "abacaba";

    cout << countPairs(s);

  

    return 0;

}



Source link

Filed Under: c programming Tagged With: •   Dynamic Programming, About Us, Advanced Data Structure, Advanced Topics, Algo ▼, Algorithm Paradigms ►, Algorithms, All Algorithms, All Data Structures, Analysis of Algorithms, Aptitude, Arrange first N natural numbers such that absolute difference between all adjacent elements > 1, Array, Backtracking, Binary Search Tree, Binary Tree, Bit Algorithms, Branch & Bound, C, Campus Ambassador Program, Campus Geek of the Month, Careers, Check if a word exists in a grid or not, Combinatorial, Company Prep, Company-wise, Competitive Programming, Compiler Design, Computer Graphics, Computer Networks, Computer Organization, Computer Organization & Architecture, Contact Us, Contests, contribute.geeksforgeeks.org, Core Subjects ►, Count All Palindromic Subsequence in a given String, Count all Prime Length Palindromic Substrings, Count number of equal pairs in a string, count number of substrings that start and end with 1., Count Numbers with N digits which consists of odd number of 0's, Count of distinct substrings of a string using Suffix Array, Count of distinct substrings of a string using Suffix Trie, Count of Numbers in a Range divisible by m and having digit d in even positions, Count of Numbers in a Range where digit d occurs exactly K times, Count of Numbers in Range where first digit is equal to last digit of the number, Count of Numbers in Range where the number does not contain more than K non zero digits, Count of Palindromic substrings in an Index range, Count of sub-sets of size n with total element sum divisible by 3, Count of substrings of a binary string containing K ones, Count palindromic characteristics of a String, Count paths with distance equal to Manhattan distance, Count the number of special permutations, Count the number of vowels occurring in all the substrings of given string, Count unordered pairs (i, Courses, CS Subjects, CS Subjects ▼, CS Subjectwise ►, CSS, Data Structures, DBMS, Deletions of "01" or "10" in binary string to make it free from "01" or "10", Design Patterns, Digital Electronics, Divide and Conquer, DS ▼, Engg. Mathematics, Experienced Interviews, Find a palindromic string B such that given String A is a subsequense of B, Find the count of palindromic sub-string of a string in its sorted form, Game Theory, GATE ▼, GATE 2019, GATE CS Corner, GATE Notes, GATE Official Papers, GBlog, Geek of the Month, Geek on the Top, Generating Lyndon words of length n, Geometric Algorithms, Given a binary string, Graph, Graph Algorithms, Greedy Algorithms, Hashing, Heap, HTML, HTML & XML, ide.geeksforgeeks.org, Internship, Internship Interviews, Internships, Interview ▼, Interview Experiences, ISRO CS Exam, j) such that product of a[i] and a[j] is power of two, Java, Java Program to print distinct permutations of a string, JavaScript, jQuery, K length words that can be formed from given characters without repetition, Languages, Languages ►, Languages ▼, Last Minute Notes, LinkedList, Longest subsequence such that adjacent elements have at least one common digit, Machine Learning, Make Binary Search Tree, Make palindromic string non-palindromic by rearranging its letters, Mathematical Algorithms, Matrix, Maximum sum from three arrays such that picking elements consecutively from same is not allowed, Microprocessor, Minimum cuts required to convert a palindromic string to a different palindromic string, Multiple Choice Quizzes, Number of moves required to guess a permutation., Number of permutations of a string in which all the occurrences of a given character occurs together, Number of submatrices with all 1s, Number of submatrices with OR value 1, Number of trailing zeroes in base 16 representation of N!, Number of triangles that can be formed with given N points, Number of unique pairs in an array, Number of ways of scoring R runs in B balls with at most W wickets, Number of ways to go from one point to another in a grid, Number of ways to select a node from each connected component, Operating Systems, palindrome, Pattern Searching, Permutations of string such that no two vowels are adjacent, PHP, Placement Course, Practice, Practice Company Questions, Privacy Policy, Program Output, Program to calculate the value of nCr Efficiently, Program to calculate the value of nPr, Project, Puzzles, Python, Queries to check if substring[L…R] is palindrome or not, Queue, Quizzes ▼, Randomized Algorithms, Rearrange the string to maximize the number of palindromic substrings, Recommended: Please try your approach on, School Programming, Searching Algorithms, Skip to content, Software Engineering, Some rights reserved, Sorting Algorithms, SQL, Stack, Strings, Students ▼, Subjective Questions, substring, Suggest an Article, Sum of (maximum element - minimum element) for all the subsets of an array., Sum of all Submatrices of a Given Matrix, Sum of bitwise AND of all submatrices, Sum of Bitwise-OR of all Submatrices, Sum of XOR of all subarrays, Testimonials, Theory of Computation, Top Topics, Topic-wise, Topicwise ►, Total number of subsets in which the product of the elements is even, Tree based DS ►, UGC NET CS Paper II, UGC NET CS Paper III, UGC NET Papers, Understanding The Coin Change Problem With Dynamic Programming, Video Tutorials, Videos, Ways to divide a binary array into sub-arrays such that each sub-array contains exactly one 1, Ways to paint N paintings such that adjacent paintings don't have same colors, Web Technology, What’s Difference?, Write an Article, Write Interview Experience

Maximum volume of cube for every person when edge of N cubes are given

Leave a Comment


Given an array of N integers which denotes the edges of N cubical structures respectively. Also given are M integers which denotes the number of peoples. The task is to find the maximum amount of volume of a cube that can be given to every person.

Note: Cubes can be cut of any shape from any of the N cubes.

Examples:

Input: a[] = {1, 1, 1, 2, 2}, m = 3
Output: 4
All three person get a slice of volume 4 each
Person 1 gets a slice of volume 4 from the last cube.
Person 2 gets a slice of volume 4 from the last cube.
Person 3 gets a slice of volume 4 from the second last cube.

Input: a[] = {2, 2, 2, 2, 2}, m = 4
Output: 8


Naive Approach: A naive approach is to first calculate the volume of all of the cubes and then linearly check for every volume that it can be distributed among all M people or not and find the maximum volume among all such volumes.

Time Complexity: O(N2)

Efficient Approach: An efficient approach is to use binary search to find the answer. Since the edge lengths are given in the array, convert them to the volume of the respective cubes.

Find the maximum volume among volumes of all of the cubes. Say, the maximum volume is maxVolume. Now, perform binary search on the range [0, maxVolume].

  • Calculate the middle value of the range, say mid.
  • Now, calculate the total number of cubes that can be cut of all of the cubes of volume mid.
  • If the total cubes that can be cut exceed the number of persons, then that amount of volume of cubes can be cut for every person, hence we check for a larger value in the range [mid+1, maxVolume].
  • If the total cubes do not exceed the number of persons, then we check for an answer in the range [low, mid-1].

Below is the implementation of the above approach:

  

#include <bits/stdc++.h>

using namespace std;

  

int getMaximumVloume(int a[], int n, int m)

{

    int maxVolume = 0;

  

    

    

    for (int i = 0; i < n; i++) {

        a[i] = a[i] * a[i] * a[i];

  

        maxVolume = max(a[i], maxVolume);

    }

  

    

    

    int low = 0, high = maxVolume;

  

    

    int maxVol = 0;

  

    

    while (low <= high) {

  

        

        int mid = (low + high) >> 1;

  

        

        int cnt = 0;

        for (int i = 0; i < n; i++) {

            cnt += a[i] / mid;

        }

  

        

        

        

        if (cnt >= m) {

  

            

            low = mid + 1;

  

            

            

            maxVol = max(maxVol, mid);

        }

  

        

        else

            high = mid - 1;

    }

  

    return maxVol;

}

  

int main()

{

    int a[] = { 1, 1, 1, 2, 2 };

    int n = sizeof(a) / sizeof(a[0]);

    int m = 3;

  

    cout << getMaximumVloume(a, n, m);

  

    return 0;

}

Time Complexity: O(N * log (maxVolume))



Striver(underscore)79 at Codechef and codeforces D


If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please Improve this article if you find anything incorrect by clicking on the “Improve Article” button below.

Article Tags :


thumb_up
Be the First to upvote.

Please write to us at contribute@geeksforgeeks.org to report any issue with the above content.


Post navigation


Previous

first_page Partition the array into three equal sum segments







Source link

Filed Under: c programming Tagged With: •   Dynamic Programming, About Us, Advanced Data Structure, Advanced Topics, Algo ▼, Algorithm Paradigms ►, Algorithms, All Algorithms, All Data Structures, Analysis of Algorithms, Aptitude, Array, Array Manipulation and Sum, Arrays, Backtracking, Binary Search, Binary Search Tree, Binary Tree, Bit Algorithms, Branch & Bound, C, Calculate the total fine to be collected, Campus Ambassador Program, Campus Geek of the Month, Careers, Check if an array is sorted and rotated, Check if X can give change to every person in the Queue, Check whether an Array is Subarray of another Array, Coin game of two corners (Greedy Approach), Company Prep, Company-wise, Competitive Programming, Compiler Design, Computer Graphics, Computer Networks, Computer Organization, Computer Organization & Architecture, Constructive Algorithms, Contact Us, Contests, contribute.geeksforgeeks.org, Convert a String to Integer Array in C/C++, Core Subjects ►, Count array elements that divide the sum of all other elements, Count distinct elements in an array, Count of pairs (x, Courses, Coviam Software Developer Internship Experience, CS Subjects, CS Subjects ▼, CS Subjectwise ►, CSS, Data Structures, DBMS, Design a Hit Counter, Design Patterns, Digital Electronics, Divide and Conquer, DS ▼, Engg. Mathematics, Experienced Interviews, Find triplets in an array whose AND is maximum, Find two numbers whose divisors are given in a random order, For each element in 1st array count elements less than or equal to it in 2nd array | Set 2, Game Theory, GATE ▼, GATE 2019, GATE CS Corner, GATE Notes, GATE Official Papers, GBlog, Geek of the Month, Geek on the Top, Generating subarrays using recursion, Geometric Algorithms, Graph, Graph Algorithms, Greedy Algorithms, Hashing, Heap, How do Dynamic arrays work?, HTML, HTML & XML, ide.geeksforgeeks.org, Internship, Internship Interviews, Internships, Interview ▼, Interview Experiences, ISRO CS Exam, Java, JavaScript, jQuery, K maximum sum combinations from two arrays, Languages, Languages ►, Languages ▼, Largest number in an array that is not a perfect cube, Largest palindromic number in an array, Largest perfect cube number in an Array, Last Minute Notes, Length of the longest alternating subarray, Length of the longest Subarray with only Even Elements, LinkedList, Longest subarray having maximum sum, Longest subsequence such that adjacent elements have at least one common digit, Machine Learning, Make all numbers of an array equal, MakeMyTrip Interview Experience 2019, Mathematical Algorithms, Matrix, Maximum even sum subsequence, Maximum length of rod for Q-th person, Maximum Sum Path in Two Arrays, Maximum sum rectangle in a 2D matrix | DP-27, Maximum triplet sum in array, Maximum value of |arr[0] - arr[1]| + |arr[1] - arr[2]| + ... +|arr[n - 2] - arr[n - 1]| when elements are from 1 to n, Maximum value of |arr[i] - arr[j]| + |i - j|, Maximum value of arr[i] % arr[j] for a given array, Merge K sorted arrays | Set 3 ( Using Divide and Conquer Approach ), Microprocessor, Minimum elements to be removed such that sum of adjacent elements is always even, Minimum number of items to be delivered, Minimum number of swaps required to sort an array | Set 2, Minimum operations required to make all the array elements equal, Multidimensional Arrays in Java, Multiple Choice Quizzes, Next greater element in same order as input, Operating Systems, Partition the array into three equal sum segments, Pattern Searching, PHP, Placement Course, Practice, Practice Company Questions, Privacy Policy, Program for K Most Recently Used (MRU) Apps, Program Output, Program to check if an array is palindrome or not using Recursion, Program to find the Hidden Number, Project, Puzzles, Python, Queue, Quizzes ▼, Randomized Algorithms, Reach the numbers by making jumps of two given lengths, Rearrange Odd and Even values in Alternate Fashion in Ascending Order, Remove duplicates from unsorted array, School Programming, Searching Algorithms, Skip to content, Sliding Window Maximum (Maximum of all subarrays of size k), Smallest perfect Cube divisible by all elements of an array, Software Engineering, Some rights reserved, Sort elements by frequency | Set 5 (using Java Map), Sorting Algorithms, SQL, Stack, Strings, Students ▼, Subjective Questions, Subsequence with maximum odd sum, Suggest an Article, Sum of all odd frequency elements in an array, Sum of minimum elements of all subarrays, Sum of XOR of all subarrays, Testimonials, Theory of Computation, Top Topics, Topic-wise, Topicwise ►, Tree based DS ►, UGC NET CS Paper II, UGC NET CS Paper III, UGC NET Papers, Video Tutorials, Videos, Web Technology, What’s Difference?, Write an Article, Write Interview Experience, y) in an array such that x < y

Primary Sidebar

Recent Posts

  • Find the minimum spanning tree with alternating colored edges
  • Engineering Chemistry Questions and Answers – Application of Colloids
  • MongoDB Beginners Tutorial
  • 10 Projects That Every Developer Should Lay Their Hands-On
  • Engineering Chemistry Questions and Answers – Detergents
  • Privacy Policy
  • About
  • Contact US

© 2019 ProProgramming
 Privacy Policy About Contact Us