Given an unsorted array a of size N of non-negative integers, find a continuous subarray which adds to a given number S.

Question

1.00/5 (4 votes)

See more:

INPUT:
The first line of the input contain an integers T denoting the number of test cases . then T test cases follows.each case consists of two lines .the first line of each test case is N and S. where N is the size of aaray and S is the sum .the second line of the test case contain N space separted intergers denoting the array elements.

output:
for each test case , in a new line,print the starting and ending positions(1 indexing) of the first such occuring subarray from the left if sum equals to subarray , else print -1.
constraints :
1<=T<=100
1<=N<=10^7
1<=A<=10^10
Example:
input:
2
5 12
1 2 3 7 5
10 15
1 2 3 4 5 6 7 8 9 10
output :
2 4
1 5

What I have tried:

#include <stdio.h>

int main()
{
    int kases;
    scanf("%d", &kases);
    int kase;
    for(kase = 1; kase <= kases; kase++) {
        int  N;
        scanf("%d", &N);
        int result[1000];
        result[0] = 1;
        int length = 1, i, j, temp, carry = 0;
        for(i = 2; i <= N; i++) {
            for(j = 0; j < length; j++) {
                temp = carry + result[j] * i;
                carry = temp / 10;
                result[j] = temp % 10;
            }
            while(carry) {
                result[j] = carry % 10;
                carry /= 10;
                j++;
            }
            length = j;
        }
        for(int i = length - 1; i >= 0; i--){
            printf("%d", result[i]);
        }
        printf("\n");
    }
    return 0;
}

Posted 8-Jan-20 9:17am

Member 14710774

Updated 7-Mar-23 8:18am

Add a Solution

Comments

phil.o 8-Jan-20 15:19pm

What is your question?

Patrice T 8-Jan-20 16:55pm

And you have a problem or a question ?

OriginalGriff 8-Jan-20 17:19pm

And?
What does it do that you didn't expect, or not do that you did?
What have you tired to find out why?
What did the debugger show?
Where are you stuck?
What help do you need?

Use the "Improve question" widget to add information to your question.

Rick York 8-Jan-20 17:59pm

You could read the input data from a file instead of entering it every time. That would make your debugging much faster and easier.

4 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Patrice T · Answer 1 · 2020-01-08T11:45:00

I see, your code is not even remotely related to the requirement, you have no comment, no question. You just want us to give you a full blowup solution, so you can claim it is yours. It is unlikely to happen.

We do not do your HomeWork.
HomeWork is not set to test your skills at begging other people to do your work, it is set to make you think and to help your teacher to check your understanding of the courses you have taken and also the problems you have at applying them.
Any failure of you will help your teacher spot your weaknesses and set remedial actions.
Any failure of you will help you to learn what works and what don't, it is called 'trial and error' learning.
So, give it a try, reread your lessons and start working. If you are stuck on a specific problem, show your code and explain this exact problem, we might help.

As programmer, your job is to create algorithms that solve specific problems and you can't rely on someone else to eternally do it for you, so there is a time where you will have to learn how to. And the sooner, the better.
When you just ask for the solution, it is like trying to learn to drive a car by having someone else training.
Creating an algorithm is basically finding the maths and make necessary adaptation to fit your actual problem.

CPallini · Answer 2 · 2020-01-08T22:08:00

The algorithm is simple, just use three variables:

beg - index of the first item of the searched subarray
end - index of the last item of the subarray
sum - sum of the subarray items

1. let beg = 0
2. let sum = array[beg]; end=beg;
3. if sum > S then 
     let beg = beg + 1; goto 2;
   else if sum == S then 
     print( beg + 1, end + 1); exit;
   else // here sum < S
     end = end + 1; sum = sum + array[end]; goto 3;

The corner case of 'subarray not found' is left as exercise.

Member 15053240 · Answer 3 · 2021-01-22T00:59:00

int s=33;
   int ch[]={1, 4, 20, 3, 10, 5};
   int n=sizeof(ch)/sizeof(ch[0]);
   int sum=0, count=1;
 for(int j=0;j<n;j++)
 { sum=0;
     for(int k=j;k<n;k++)
     {
         sum=sum+ch[k];//5 10 12
         if(sum==s)
         {printf("Sum found between indexes %d %d\n",j,k);
             count=count+1;
         }
     }
 }
 if(count<=1)
 {  printf("no subarray found");}

Member 15944545 · Answer 4 · 2023-03-07T08:18:00

#include <iostream>
using namespace std;
int lower(int Arr[], int N, int S)
{
int flag = -1;
for (int i = 0; i < N; i++)
{
int sum = 0;
for (int j = i; j < N; j++)
{
sum = sum + Arr[j];
if (sum == S && flag == -1)
{
flag = i;
}
}
}
return flag;
}
int upper(int Arr[], int N, int S)
{
int flag = -1;
for (int i = 0; i < N; i++)
{
int sum = 0;
for (int j = i; j < N; j++)
{
sum = sum + Arr[j];
if (sum == S && flag == -1)
{
flag = j;
}
}
}
return flag;
}
int main()
{
int N;
cout << "Enter the size of array 😄 :: " << endl;
cin >> N;
int A[N];
cout << "Enter " << N << " integers 😄 :: " << endl;
for (int i = 0; i < N; i++)
{
cin >> A[i];
}
int S;
cout << "Enter the sum to be found 😄 :: " << endl;
cin >> S;
int Lower, Upper;
Lower = lower(A, N, S);
Upper = upper(A, N, S);
if (Lower == -1 && Upper == -1)
{
cout << "No sub array found 🥲 " << endl;
}
else
{
for (int i = Lower; i <= Upper; i++)
{
cout << A[i] << " ";
}
}
return 0;
}

Given an unsorted array a of size N of non-negative integers, find a continuous subarray which adds to a given number S.

4 solutions

Solution 1

Solution 2

Solution 5

Solution 6

Add your solution here

Preview 0