Horje
Count ways to represent N as sum of palindromic integers which do not have digit 1

Given a positive integer N, the task is to find the number of distinct ways to express N as a sum of positive palindromic integers which do not have the digit 1 in them.

Note: As the answer can be quite large, print it modulo 109+7.

Examples:

Input: N = 4
Output: 2
Explanation: Following are the 2 Multisets that satisfy the condition:
1. 2+2 = 4
2. 4 = 4

Input: N = 8
Output: 7
Explanation: Following are the distinct Multisets that satisfy the condition:
1. 2+2+2+2 = 8
2. 2+3+3 = 8
3. 2+2+4 = 8
4. 4+4 = 8
5. 3+5 = 8
6. 2+6 = 8
7. 8 = 8

Approach:

Here each palindromic integers that don’t have the digit 1 can come an infinite number of times. (Repetition allowed), this is what we call Unbounded Knapsack. 

  • We have 2 choices for a palindromic number without a digit 1, either i) to include, or ii) to exclude.  But here, the inclusion process is not for just once; we can include any palindromic number without a single one any number of times until N < Sum.
  • Basically, If we are at V[m], we can take as many instances of that integer ( unbounded inclusion ) i.e count(V, m, sum – V[m] )  then we move to V[m-1]. After moving to V[m-1], we can’t move back and can’t make choices for V[m] i.e count(V, m-1, sum).
  • To find the total number of ways, so we have to add these 2 possible choices, i.e count(V, m, sum – S[m] ) + count(V, m-1, sum ).

Follow the steps given below for a better approach:

  • Declare a vector V to store all the numbers less than N which are palindrome and do not contain the digit 1.
  • Use a recursive function and in each recursive call, pass the vector V and the index integer(m) and the value of N (sum).
  • In each iteration, perform two recursive calls,  
    • In one of them decrease m(index element) by 1 and 
    • On the other one decrease the value of sum by V[m].
      • If the sum became 0 then return 1. So it will be added to the final answer which we return.
    • If sum or m is less than 0, then return 0.

Below is the implementation of the above approach.
 

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
int mod = 1e9 + 7;
 
// Function for checking if
// the given integer is palindrome or not
bool isPalindrome(int i)
{
    string x = to_string(i);
    int n = x.length();
    int cnt_one = 0;
    for (int i = 0; i < n / 2; i++) {
        if (x[i] == '1') {
            cnt_one++;
        }
        if (x[i] == x[n - 1 - i]) {
            continue;
        }
        else {
            return false;
        }
    }
    if (cnt_one == 1)
        return false;
    return true;
}
 
// Helper function
int helper(vector<int>& V, int m, int sum)
{
    // Base cases
 
    // As there is 1 way which is the empty set
    if (sum == 0)
        return 1;
 
    // If sum is negative then there is no way
    if (sum < 0)
        return 0;
 
    // If no integer left and the sum is not 0
    // then we cannot make sum 0
    if (m < 0 && sum > 0)
        return 0;
 
    return (helper(V, m - 1, sum) % mod
            + helper(V, m, sum - V[m]) % mod)
           % mod;
}
 
// Function to find the count of ways
int countMultiSet(int N)
{
    vector<int> V;
 
    // Vector storing the palindromic number till n
    for (int i = 2; i <= N; i++) {
        if (isPalindrome(i)) {
            V.push_back(i);
        }
    }
 
    // Calling the helper function
    return helper(V, V.size() - 1, N);
}
 
// driver function
int main()
{
    int N = 8;
 
    // calling the function
    cout << countMultiSet(N);
    return 0;
}

Java

/*package whatever //do not write package name here */
import java.io.*;
import java.util.ArrayList;
 
class GFG {
 
  // Function for checking if
  // the given integer is palindrome or not
  static boolean isPalindrome(Integer i)
  {
    String x = i.toString();
    int n = x.length();
    int cnt_one = 0;
    for (int j = 0; j < n / 2; i++) {
      if (x.charAt(j) == '1') {
        cnt_one++;
      }
      if (x.charAt(j) == x.charAt(n - 1- j)) {
        continue;
      }
      else {
        return false;
      }
    }
    if (cnt_one == 1)
      return false;
    return true;
  }
 
  // Helper function
  static int helper(ArrayList<Integer> V, int m, int sum)
  {
    // Base cases
 
    // As there is 1 way which is the empty set
    if (sum == 0)
      return 1;
 
    // If sum is negative then there is no way
    if (sum < 0)
      return 0;
 
    // If no integer left and the sum is not 0
    // then we cannot make sum 0
    if (m < 0 && sum > 0)
      return 0;
 
    return (helper(V, m - 1, sum) % (1000000007)
            + helper(V, m, sum - V.get(m)) % (1000000007))
      % (1000000007);
  }
 
  // Function to find the count of ways
  static int countMultiSet(int N)
  {
    ArrayList<Integer> V = new ArrayList<Integer>();
 
    // List storing the palindromic number till n
    for (int i = 2; i <= N; i++) {
      if (isPalindrome(i)) {
        V.add(i);
      }
    }
 
    // Calling the helper function
    return helper(V, V.size() - 1, N);
  }
    public static void main (String[] args) {
       int N = 8;
 
      // calling the function
      System.out.println(countMultiSet(N));
    }
}
 
// This code is contributed by hrithikgarg03188.

Python3

# Python3 code to implement the approach
mod = 1e9 + 7
 
# Function for checking if
# the given integer is palindrome or not
def isPalindrome(i):
    x = str(i)
    n = len(x)
    cnt_one = 0
 
    for i in range(0, int(n/2)):
 
        if (x[i] is '1'):
            cnt_one = cnt_one+1
        if (x[i] is x[n - 1 - i]):
            continue
        else:
            return false
    if (cnt_one is 1):
        return False
    return True
# Helper function
def helper(V, m, sum):
    # Base cases
 
    # As there is 1 way which is the empty set
    if (sum is 0):
        return 1
 
    # If sum is negative then there is no way
    if (sum < 0):
        return 0
 
    # If no integer left and the sum is not 0
    # then we cannot make sum 0
    if (m < 0 and sum > 0):
        return 0
 
    return (helper(V, m - 1, sum) % mod + helper(V, m, sum - V[m]) % mod) % mod
 
# Function to find the count of ways
def countMultiSet(N):
    V = []
 
    # Vector storing the palindromic number till n
    for i in range(2, N+1):
        if (isPalindrome(i)):
            V.append(i)
 
    # Calling the helper function
    return helper(V, len(V) - 1, N)
 
# driver function
N = 8
 
# calling the function
ans = countMultiSet(N)
print(int(ans))
 
# This code is contributed by akashish__

C#

using System;
using System.Collections.Generic;
 
public class GFG {
 
  // Function for checking if
  // the given integer is palindrome or not
  public static bool isPalindrome(int i)
  {
    string x = i.ToString();
    int n = x.Length;
    int cnt_one = 0;
    for (int j = 0; j < n / 2; i++) {
      if (x[j] == '1') {
        cnt_one++;
      }
      if (x[j] == x[n - 1 - j]) {
        continue;
      }
      else {
        return false;
      }
    }
    if (cnt_one == 1)
      return false;
    return true;
  }
 
  // Helper function
  public static int helper(List<int> V, int m, int sum)
  {
    // Base cases
 
    // As there is 1 way which is the empty set
    if (sum == 0)
      return 1;
 
    // If sum is negative then there is no way
    if (sum < 0)
      return 0;
 
    // If no integer left and the sum is not 0
    // then we cannot make sum 0
    if (m < 0 && sum > 0)
      return 0;
 
    return (helper(V, m - 1, sum) % (1000000007)
            + helper(V, m, sum - V[m]) % (1000000007))
      % (1000000007);
  }
 
  // Function to find the count of ways
  public static int countMultiSet(int N)
  {
    List<int> V = new List<int>();
 
    // List storing the palindromic number till n
    for (int i = 2; i <= N; i++) {
      if (isPalindrome(i)) {
        V.Add(i);
      }
    }
 
    // Calling the helper function
    return helper(V, V.Count - 1, N);
  }
 
  static public void Main()
  {
 
    int N = 8;
 
    // calling the function
    Console.WriteLine(countMultiSet(N));
  }
}
 
// This code is contributed by akashish__

Javascript

<script>
        // JavaScript code for the above approach
 
  // Function for checking if
  // the given integer is palindrome or not
  function isPalindrome(i)
  {
    let x = i.toString();
    let n = x.length;
    let cnt_one = 0;
    for (let j = 0; j < Math.floor(n / 2); i++) {
      if (x.charAt(j) == '1') {
        cnt_one++;
      }
      if (x.charAt(j) == x.charAt(n - 1- j)) {
        continue;
      }
      else {
        return false;
      }
    }
    if (cnt_one == 1)
      return false;
    return true;
  }
 
  // Helper function
  function helper(V,  m,  sum)
  {
    // Base cases
 
    // As there is 1 way which is the empty set
    if (sum == 0)
      return 1;
 
    // If sum is negative then there is no way
    if (sum < 0)
      return 0;
 
    // If no integer left and the sum is not 0
    // then we cannot make sum 0
    if (m < 0 && sum > 0)
      return 0;
 
    return (helper(V, m - 1, sum) % (1000000007)
            + helper(V, m, sum - V[m]) % (1000000007))
      % (1000000007);
  }
 
  // Function to find the count of ways
  function countMultiSet( N)
  {
    let V = new Array();
 
    // List storing the palindromic number till n
    for (let i = 2; i <= N; i++) {
      if (isPalindrome(i)) {
        V.push(i);
      }
    }
 
    // Calling the helper function
    return helper(V, V.length - 1, N);
  }
 
// Driver Code
    let N = 8;
 
      // calling the function
      document.write(countMultiSet(N));
       
      // This code is contributed by sanjoy_62.
    </script>

Output

7

Time Complexity: O(2M) M is the size of the vector V 
Auxiliary Space: O(M) 


 


Reffered: https://www.geeksforgeeks.org

Mathematical

Related
Count of N digit numbers with at least one digit as K Count of N digit numbers with at least one digit as K
Parity of final value after repeated circular removal of Kth Integer Parity of final value after repeated circular removal of Kth Integer
Find minimum and maximum number of terms to divide N as sum of 4 or 6 Find minimum and maximum number of terms to divide N as sum of 4 or 6
Compute nCr % p | Set 4 (Chinese Remainder theorem with Lucas Theorem) Compute nCr % p | Set 4 (Chinese Remainder theorem with Lucas Theorem)
Find the largest co-prime fraction less than the given fraction Find the largest co-prime fraction less than the given fraction

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 16



 

Horje