Minimum pluses required to make the equation (x = y) correct

-
4

Problem Statement:

Given an equation “x=y”, for example, “111=12”, you need to add pluses inside x to make the equation correct. In our example “111=12”, we can add one plus “11+1=12” and the equation becomes correct. You need to find the minimum number of pluses to add to x to make the equation correct. If there is no answer print -1.

Note that the value of y won’t exceed 5000. The numbers in the corrected equation may contain arbitrary amounts of leading zeros.

Input Format The first line contains a string, A as described in the problem statement.

Constraints 1 <= len(A) <= 10^3

I tried the recursive approach. Which is for every character in the 'x', I have two options I can include the plus sign next to the current digit or move to the next digit (by including the current digit with the next digit) I checked all the combinations and found the minimum pluses. As you know, this is exponential in complexity. I'm not able to apply dynamic programming for this problem as I can't think of the states for the dynamic programming.

I know this problem can be solved by dynamic programming. But, I don't know how to identify the state and the transition.

c++ algorithm c++14 dynamic-programming
Share
Improve this question
5
  • 2
    This is not the right site to ask for help on solving general problems. It's a site for asking specific questions about programming. – super Apr 12 at 16:03
  • 8
    @super: Huh? This is a specific algorithmic problem, which is entirely on-topic for SO according to the tour (it lists "Software algorithms"). The only problem with this question is that the OP didn't show their attempts at solving it. – Yakov Galka Apr 12 at 16:06
  • @YakovGalka If you want to call copy-pasting some programming quiz/problem a specific algorithmic problem you are more generous then me. Also, I think that fact that it fails to show any attempt at a solution or what parts of the problem OP is having an issue with makes it anything but specific. I could have worded that more carefully or precise, but I guess seeing this kind of post dumps 15 times a day makes you less eager to do so. – super Apr 12 at 16:14
  • 1
    It does not show any effort, that part is true and also it should be more specific. However, this does qualify a programming problem though. @Naveen Kumar Please mention your efforts in the question and be more specific on the part where you are facing problem. – AKSingh Apr 12 at 16:21
  • 1
    @AKSingh, Thanks for your response. I tried the recursive approach. Which is for every character in the 'x', I have two options I can include the plus sign next to the current digit or move to the next digit (by including the current digit with the next digit) I checked all the combinations and found the mininum pluses. As you know, this is exponential in complexity. I'm not able to apply dynamic programming for this problem as I can't think of the states for the dp. – Naveen Kumar Apr 12 at 16:39

Comments

Post a Comment

Popular posts from this blog

Meaning of `{}` for return expression

-
15 1 I found by accident that the following compiles: #include <string> #include <iostream> class A{ int i{}; std::string s{}; public: A(int _i, const std::string& _s) : i(_i), s(_s) { puts("Called A(int, const std::string)"); } }; A foo(int k, const char* cstr){ return {k, cstr}; // (*) } int main(){ auto a = foo(10, "Hi!"); return 0; } The line of interest is (*). I guess the function foo is equivalent to: A foo(int k, const char* str){ return A(k, cstr); } However, is there a special name for this mechanism in (*)? Or is it just the simple fact that the compiler knows which constructor to call due to the return type? ...
Read more

Get current scroll position of ScrollView in React Native

-
Is it possible to get the current scroll position, or the current page of a <ScrollView> component in React Native? So something like: <ScrollView horizontal={true} pagingEnabled={true} onScrollAnimationEnd={() => { // get this scrollview's current page or x/y scroll position }}> this.state.data.map(function(e, i) { <ImageCt key={i}></ImageCt> }) </ScrollView> Try. <ScrollView onScroll={this.handleScroll} /> And then: handleScroll: function(event: Object) { console.log(event.nativeEvent.contentOffset.y); }, Disclaimer: what follows is primarily the result of my own experimentation in React Native 0.50. The ScrollView documentation is currently missing a lot of the information covered below; for instance onScrollEndDrag is completely undocumented. Since everything here relies upon undocumented behaviour, I can unfortunately make no promises that this information will remain correct a ...
Read more

flutter websocket connection issue

-
I am trying to develop a flutter app which connects to the server and exchanges data using websocket. The server is in .Net Core and using Asp.Net Core Websockets to implement this functionality. The problem I am facing is, my flutter app is not able to connect to the server and throws following error. E/flutter (31498): [ERROR:topaz/lib/tonic/logging/dart_error.cc(16)] Unhandled exception: E/flutter (31498): WebSocketChannelException: WebSocketChannelException: WebSocketException: Connection to 'http://127.0.0.1/client#' was not upgraded to websocket E/flutter (31498): #0 new IOWebSocketChannel._withoutSocket.<anonymous closure> (package:web_socket_channel/io.dart:83:24) E/flutter (31498): #1 _invokeErrorHandler (dart:async/async_error.dart:13:29) E/flutter (31498): #2 _HandleErrorStream._handleError (dart:async/stream_pipe.dart:286:9) E/flutter (31498): #3 _ForwardingStreamSubscription._handleError (dart:async/stream_pipe.dart:168:13) E/flutter (3149...
Read more