Given integers, L and R, the task is to find the ?f(x) for all L to R, where f(x) is defined for number as f(x) = (sum of digits on odd positions of x – the sum of digits on even positions of x).
Examples:
Input: L =10, R =15
Output: -9
Explanation:
- f(10) = 1 – 0 = 1
- f(11) = 1 – 1 = 0
- f(12) = 1 – 2 = -1
- f(13) = 1 – 3 = -2
- f(14) = 1 – 4 = -3
- f(15) = 1 – 5 = -4
Total sum = f(10) + f(11) + f(12) + f(13) + f(14) + f(15) = 1 + 0 – 1 – 2 – 3 – 4 = – 9
Input: L = 101, R = 105
Output: 20
Explanation:
- f(101) = 1 – 0 + 1 = 2
- f(102) = 1 – 0 + 2 = 3
- f(103) = 1 – 0 + 3 = 4
- f(104) = 1 – 0 + 4 = 5
- f(105) = 1 – 0 + 5 = 6
Total sum = f(101) + f(102) + f(103) + f(104) + f(105) = 2 + 3 + 4 + 5 + 6 = 20
Naive approach: The basic way to solve the problem is as follows:
The basic way to solve this problem is to generate all possible combinations by using a recursive approach.
Time Complexity: O(N10)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following idea:
Dynamic programming can be used to solve this problem
- dp[i][j][k][l] represents sum of forming i digit number with j as tight condition, k as current sum and l tells whether current position odd or even of number.
- It can be observed that the recursive function is called exponential times. That means that some states are called repeatedly. So the idea is to store the value of each state.
- This can be done using by store the value of a state and whenever the function is called, return the stored value without computing again.
Follow the steps below to solve the problem:
- Create a recursive function that takes four parameters i representing the current position to be filled, j as the tight condition, k as the current sum, and l which indicates the current position is odd or even.
- Call recursive function for all 0 to 9.
- Create an 4d array of dp[20][2][360][2] with initially filled with -1.
- If the answer for a particular state is computed then save it in dp[i][j][k][l].
- If the answer for a particular state is already computed then just return dp[i][j][k][l].
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// DP table initialized with -1int dp[20][2][360][2];// Recursive Function to find numbers// summation of f(x) in the range L to Rint recur(int i, int j, int k, int l, string& a){ // Base case if (i == a.size()) { return k; } // If answer for current state is // already calculated then just return // dp[i][j][k][l] +180 is offset to // store negative values if (dp[i][j][k + 180][l] != -1) return dp[i][j][k + 180][l]; // Answer initialized with zero int ans = 0; // MaxValue that can be traversed int maxValue = j == 1 ? a[i] - 48 : 9; // If first non integer digit // not taken if (l == 0) { // Traversing from 0 to maxValue for (int digit = 0; digit <= maxValue; digit++) { // Calling recursive function // for maxValue digit if (digit == maxValue) ans += recur(i + 1, j, k + digit, 1, a); // Calling recursive function // for non-zero digit else if (digit != 0) ans += recur(i + 1, 0, k + digit, 1, a); // Calling recursive function // for zero else ans += recur(i + 1, 0, k, 0, a); } } // If first non integer digit taken else { // Traversing from 0 to maxValue for (int digit = 0; digit <= maxValue; digit++) { // Calling recursive function // for maxValue digit and // flipping l that is current // position is odd or even and // turn them into even or odd. if (digit == maxValue) ans += recur(i + 1, j, k + (l == 1 ? -digit : digit), l == 1 ? 2 : 1, a); // Calling recursive function // for non max value digit and // flipping l that is current // position is odd or even and // turn them into even or odd else ans += recur(i + 1, 0, k + (l == 1 ? -digit : digit), l == 1 ? 2 : 1, a); } } // Save and return dp value return dp[i][j][k + 180][l] = ans;}// Function to find numbers// summation of f(x) in the range L to Rint findfxfromLtoR(int A, int B){ // Initializing dp array with - 1 memset(dp, -1, sizeof(dp)); A--; string L = to_string(A), R = to_string(B); // f(x) for the range 0 to L int ans1 = recur(0, 1, 0, 0, L); // Initializing dp array with - 1 memset(dp, -1, sizeof(dp)); // f(x) for the range 0 to R int ans2 = recur(0, 1, 0, 0, R); // Difference of ans2 and ans1 // will generate answer for required range return ans2 - ans1;}// Driver Codeint main(){ // Input 1 int L = 10, R = 15; // Function Call cout << findfxfromLtoR(L, R) << endl; // Input 2 int L1 = 101, R1 = 105; // Function Call cout << findfxfromLtoR(L1, R1) << endl; return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { // DP table initialized with -1 static int[][][][] dp = new int[200][20][500][20]; // Recursive Function to find numbers // summation of f(x) in the range L to R public static int recur(int i, int j, int k, int l, String a) { // Base case if (i == a.length()) { return k; } // If answer for current state is already calculated // then just return dp[i][j][k][l] +180 is offset to // store negative values if (dp[i][j][k + 180][l] != -1) return dp[i][j][k + 180][l]; // Answer initialized with zero int ans = 0; // MaxValue that can be traversed int maxValue = j == 1 ? a.charAt(i) - 48 : 9; // If first non integer digit not taken if (l == 0) { // Traversing from 0 to maxValue for (int digit = 0; digit <= maxValue; digit++) { // Calling recursive function // for maxValue digit if (digit == maxValue) ans += recur(i + 1, j, k + digit, 1, a); // Calling recursive function // for non-zero digit else if (digit != 0) ans += recur(i + 1, 0, k + digit, 1, a); // Calling recursive function // for zero else ans += recur(i + 1, 0, k, 0, a); } } // If first non integer digit taken else { // Traversing from 0 to maxValue for (int digit = 0; digit <= maxValue; digit++) { // Calling recursive function // for maxValue digit and // flipping l that is current // position is odd or even and // turn them into even or odd. if (digit == maxValue) { ans += recur( i + 1, j, k + (l == 1 ? -digit : digit), l == 1 ? 2 : 1, a); } // Calling recursive function // for non max value digit and // flipping l that is current // position is odd or even and // turn them into even or odd else ans += recur( i + 1, 0, k + (l == 1 ? -digit : digit), l == 1 ? 2 : 1, a); } } // Save and return dp value return dp[i][j][k + 180][l] = ans; } // Function to find numbers // summation of f(x) in the range L to R public static int findfxfromLtoR(int A, int B) { // Initializing dp array with - 1 for (int[][][] dp1 : dp) { for (int[][] dp2 : dp1) { for (int[] dp3 : dp2) { Arrays.fill(dp3, -1); } } } A--; String L = Integer.toString(A); String R = Integer.toString(B); // f(x) for the range 0 to L int ans1 = recur(0, 1, 0, 0, L); // Initializing dp array with - 1 for (int[][][] dp1 : dp) { for (int[][] dp2 : dp1) { for (int[] dp3 : dp2) { Arrays.fill(dp3, -1); } } } // f(x) for the range 0 to R int ans2 = recur(0, 1, 0, 0, R); // Difference of ans2 and ans1 // will generate answer for required range return ans2 - ans1; } public static void main(String[] args) { // Input 1 int L = 10, R = 15; // Function Call System.out.println(findfxfromLtoR(L, R)); // Input 2 int L1 = 101, R1 = 105; // Function Call System.out.println(findfxfromLtoR(L1, R1)); }}// This code is contributed by lokesh. |
Python3
# DP table initialized with -1dp = [[[[-1 for _ in range(2)] for _ in range(360)] for _ in range(2)] for _ in range(20)]# Recursive Function to find numbers# summation of f(x) in the range L to Rdef recur(i, j, k, l, a): # Base case if i == len(a): return k # If answer for current state is # already calculated then just return # dp[i][j][k][l] +180 is offset to # store negative values if dp[i][j][k + 180][l] != -1: return dp[i][j][k + 180][l] # Answer initialized with zero ans = 0 # MaxValue that can be traversed maxValue = int(a[i]) if j == 1 else 9 # If first non integer digit # not taken if l == 0: # Traversing from 0 to maxValue for digit in range(maxValue + 1): # Calling recursive function # for maxValue digit if digit == maxValue: ans += recur(i + 1, j, k + digit, 1, a) # Calling recursive function # for non-zero digit elif digit != 0: ans += recur(i + 1, 0, k + digit, 1, a) # Calling recursive function # for zero else: ans += recur(i + 1, 0, k, 0, a) # If first non integer digit taken else: # Traversing from 0 to maxValue for digit in range(maxValue + 1): # Calling recursive function # for maxValue digit and # flipping l that is current # position is odd or even and # turn them into even or odd. if digit == maxValue: ans += recur(i + 1, j, (k - digit if l == 1 else k + digit), 2 if l == 1 else 1, a) # Calling recursive function # for non max value digit and # flipping l that is current # position is odd or even and # turn them into even or odd else: ans += recur(i + 1, 0, (k - digit if l == 1 else k + digit), 2 if l == 1 else 1, a) # Save and return dp value dp[i][j][k + 180][l] = ans return ans# Function to find numbers# summation of f(x) in the range L to Rdef findfxfromLtoR(A, B): A -= 1 L = str(A) R = str(B) # f(x) for the range 0 to L ans1 = recur(0, 1, 0, 0, L) # Initializing dp array with - 1 dp = [[[[-1 for _ in range(2)] for _ in range(360)] for _ in range(2)] for _ in range(20)] # f(x) for the range 0 to R ans2 = recur(0, 1, 0, 0, R) # Difference of ans2 and ans1 # will generate answer for required range return ans2 - ans1# Driver Codeif __name__ == '__main__': # Input 1 L = 10 R = 15 # Function Call print(findfxfromLtoR(L, R)) # Input 2 L1 = 101 R1 = 105 # Function Call print(findfxfromLtoR(L1, R1))# This code is contributed by lokeshpotta20. |
C#
// C# implementation of the above approachusing System;using System.Collections.Generic;class GFG { // DP table initialized with -1 static int[ , , ,] dp=new int[200, 20, 500, 20]; // Recursive Function to find numbers // summation of f(x) in the range L to R static int recur(int i, int j, int k, int l, string a) { // Base case if (i == a.Length) { return k; } // If answer for current state is // already calculated then just return // dp[i][j][k][l] +180 is offset to // store negative values if (dp[i,j,k + 180,l] != -1) return dp[i,j,k + 180,l]; // Answer initialized with zero int ans = 0; // MaxValue that can be traversed int maxValue = j == 1 ? a[i] - 48 : 9; // If first non integer digit // not taken if (l == 0) { // Traversing from 0 to maxValue for (int digit = 0; digit <= maxValue; digit++) { // Calling recursive function // for maxValue digit if (digit == maxValue) ans += recur(i + 1, j, k + digit, 1, a); // Calling recursive function // for non-zero digit else if (digit != 0) ans += recur(i + 1, 0, k + digit, 1, a); // Calling recursive function // for zero else ans += recur(i + 1, 0, k, 0, a); } } // If first non integer digit taken else { // Traversing from 0 to maxValue for (int digit = 0; digit <= maxValue; digit++) { // Calling recursive function // for maxValue digit and // flipping l that is current // position is odd or even and // turn them into even or odd. if (digit == maxValue) ans += recur(i + 1, j, k + (l == 1 ? -digit : digit), l == 1 ? 2 : 1, a); // Calling recursive function // for non max value digit and // flipping l that is current // position is odd or even and // turn them into even or odd else ans += recur(i + 1, 0, k + (l == 1 ? -digit : digit), l == 1 ? 2 : 1, a); } } // Save and return dp value return dp[i,j,k + 180,l] = ans; } // Function to find numbers // summation of f(x) in the range L to R static int findfxfromLtoR(int A, int B) { // Initializing dp array with - 1 for(int i=0; i<200; i++) { for(int j=0; j<20; j++) { for(int k=0; k<500; k++) { for(int l=0; l<20; l++) dp[i,j,k,l]=-1; } } } A--; string L = A.ToString(), R = B.ToString(); // f(x) for the range 0 to L int ans1 = recur(0, 1, 0, 0, L); // Initializing dp array with - 1 for(int i=0; i<200; i++) { for(int j=0; j<20; j++) { for(int k=0; k<500; k++) { for(int l=0; l<20; l++) dp[i,j,k,l]=-1; } } } // f(x) for the range 0 to R int ans2 = recur(0, 1, 0, 0, R); // Difference of ans2 and ans1 // will generate answer for required range return ans2 - ans1; } // Driver Code public static void Main() { // Input 1 int L = 10, R = 15; // Function Call Console.WriteLine(findfxfromLtoR(L, R)); // Input 2 int L1 = 101, R1 = 105; // Function Call Console.WriteLine(findfxfromLtoR(L1, R1)); }}// This code is contributed by poojaagarwal2. |
Javascript
// JavaScript code to implement the approach// DP table initialized with -1let dp = new Array(200);for (let i = 0; i < 200; i++) { dp[i] = new Array(20); for (let j = 0; j < 20; j++) { dp[i][j] = new Array(500); for (let k = 0; k < 500; k++) { dp[i][j][k] = new Array(20).fill(-1); } }}// Recursive Function to find numbers// summation of f(x) in the range L to Rfunction recur(i, j, k, l, a){ // Base case if (i === a.length) { return k; } // If answer for current state is already calculated // then just return dp[i][j][k][l] +180 is offset to // store negative values if (dp[i][j][k + 180][l] !== -1) { return dp[i][j][k + 180][l]; } // Answer initialized with zero let ans = 0; // MaxValue that can be traversed let maxValue = j === 1 ? Number(a[i]) : 9; // If first non integer digit not taken if (l === 0) { // Traversing from 0 to maxValue for (let digit = 0; digit <= maxValue; digit++) { // Calling recursive function // for maxValue digit if (digit === maxValue) { ans += recur(i + 1, j, k + digit, 1, a); } // Calling recursive function // for non-zero digit else if (digit !== 0) { ans += recur(i + 1, 0, k + digit, 1, a); } // Calling recursive function // for zero else { ans += recur(i + 1, 0, k, 0, a); } } } else { // Traversing from 0 to maxValue for (let digit = 0; digit <= maxValue; digit++) { // Calling recursive function // for maxValue digit and // flipping l that is current // position is odd or even and // turn them into even or odd. if (digit === maxValue) { ans += recur(i + 1, j, k + (l === 1 ? -digit : digit), l === 1 ? 2 : 1, a); } // Calling recursive function // for non max value digit and // flipping l that is current // position is odd or even and // turn them into even or odd else { ans += recur(i + 1, 0, k + (l === 1 ? -digit : digit), l === 1 ? 2 : 1, a); } } } // Save and return dp value return dp[i][j][k + 180][l] = ans;}// Function to find numbers summation of f(x) in the range L to Rfunction findfxfromLtoR(A, B) { // Initializing dp array with - 1 dp.forEach(dp1 => dp1.forEach(dp2 => dp2.forEach(dp3 => dp3.fill(-1)))); A--; let L = A.toString(); let R = B.toString(); // f(x) for the range 0 to L let ans1 = recur(0, 1, 0, 0, L); // Initializing dp array with - 1 dp.forEach(dp1 => dp1.forEach(dp2 => dp2.forEach(dp3 => dp3.fill(-1)))); // f(x) for the range 0 to R let ans2 = recur(0, 1, 0, 0, R); // Difference of ans2 and ans1 will generate answer for required range return ans2 - ans1;}// Input 1L = 10;R = 15;// Function callconsole.log(findfxfromLtoR(L, R) + "<br>");// Input 2L1 = 101;R1 = 105;// Function callconsole.log(findfxfromLtoR(L1, R1));// This code is contributed by lokeshmvs21. |
Output
-9 20
Time Complexity: O(log(R – L) * M), where M is the maximum value of f(x)
Auxiliary Space: O(log(R – L) * M)
Related Articles:
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
