Update coinProblem.py

[rishi457]

In this optimized version of the code, we have improved the efficiency of calculating the number of ways to make change for a given amount 'n' using a set of coin denominations specified in the 'arr' array. Let's walk through the key changes and improvements:

1. Switching to 1D Array:

   • We have replaced the 2D array 'table' with a 1D list called 'table'.
   • This change simplifies the code and reduces memory consumption because we only need to keep track of the number of ways to make change for each amount from 0 to 'n'.

2. Initialization:

   • We initialize 'table[0]' to 1. This represents the base case where there is one way to make change for an amount of 0, which is by not using any coins.

3. Iterative Update:

   • We iterate through the coin denominations in the 'arr' array and the amounts from 'S[i]' to 'n'.
   • For each coin denomination, we iteratively update 'table[j]' by adding 'table[j - S[i]]'. This represents the number of ways to make change for 'j' by either including the current coin denomination 'S[i]' or excluding it.

By implementing these changes, we have reduced the time complexity of the code to O(n*m), where 'n' is the target amount and 'm' is the number of coin denominations. This optimization simplifies the code while making it more memory-efficient and faster for larger input values, providing a scalable solution for solving the Coin Change Problem.