Post Only Coding Problems & Solutions Here | All Coding Guru's Dig In

SaM · October 20, 2019, 9:23am

ALL CODING PROBLEMS & SOLUTION PLATFORM UNDER ONE ROOF!

Hello 1Hackers

Proposing a collaborative way to learn and grow as a programmer or a way to ace your next coding interview.
We can share a daily coding problem (Not a CP level ) but the one that covers the basics and we generally face in coding interview topics may range from number theory, arrays, pointers, recursion, trees, linked list, hash table, and whatnot.

Each day one of us can give a problem and in the end, if no one is able to figure out the solution, the answer shall be posted by the person.

This can be a good mind gym. we can use this site to share the code we are working and help to solve doubts. All in this thread.

https://www.tutorialspoint.com/compile_cpp_online.php

So if you feel okay with this. Post your Coding problems here, and time to time, Experienced members that moving around my humble request to them to please Dig in and solve as many problems you can to help and for educational propose only.

Posting Rules:

Keep the thread active on a daily basis.
Don’t post more than 2 problems per 24 hours.
Don’t post more than 2 replies in a row.
Don’t post outside sites to provide the solution.
keep the thread on the topic & keep it clean from outside links.

Let’s make this place bright and helpful for peoples those who willing to get solutions, Let’s become goodwill for them to provide solutions about coding

HAPPY LEARNING! LET’S GET STARTED!

Darklooter · October 20, 2019, 9:36am

Hello @sam thank you for approving this . Now moving on here is todays 1st coding problem:

Topic covered: Arrays/vectors PROBLEM 1

Best of luck

Darklooter · October 20, 2019, 5:34pm

Here is the solution to the problem 1.

If you will observe the problem the first thing which must have came to your mind must be to iterate & increment each element of array again and again till all the element became greater than comperative value “k” .

like array for give array {1 , 2 , 5} to make all element greater than k =4, it wil be like
// increment all elements by 1 so array will be {2,3,6} count=1;
// increment all elements by 1 so array will be {3,4,7} count=2; (see 1st element is still less than k ).
increment all elements by 1 so array will be {4,5,8} count=3;

So the answer will be 3.

Actually the this is a niave and time consuming approache which also make coding this logic difficult. If you will see this problem carefully then you will notice that you only have to increment the smallest element in array till it is greater than or equal to given value of K.
Like for array {1,2,5} and k=4. The increment the lowest value i.e 1 (one by one till it become 4 ) then only print how many steps it tooks to make it equal to K.
in simple word ans= k-(smallest value).

Here is my C++ implementation.
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;cin>>n; //no of turns
while(n>0)
{
int array_size,compare;
cin>>array_size>>compare;

		vector<int> v; 
		v.resize(array_size);
		for (int i = 0; i < array_size; ++i)
		{
			cin>>v[i]; //storing elemnt of arrays.
		}
		sort(v.begin(),v.end()); //sorting array so lowest value will come on 1st position.

		if(v[0]<compare){ // k-smallest value 
		cout<<compare-v[0]<<endl;
		}
		else{
			cout<<0<<endl;
		}
		--n;
	}
	return 0;
}

I hope this helps, looking forward for your question/new coding problems.
THANKS

Ajisafe_Eniola · October 20, 2019, 6:01pm

Can this be posted in other languages ?

Summer_Jance · October 20, 2019, 6:55pm

Find the min_element in the array , sequential search O(N) , sorting may lead to O(NlogN) in worst case

K - min_element gives out the seconds

Note: Edge cases what if the min_element larger than K? return 0

Darklooter · October 20, 2019, 8:31pm

Yes you can post in any languages and kindly be sure if you are posting a solution try to explain it in details.

I have not studied maps yet.but thanks for adding .if possible try to add explanation with your codes.

Yes. If you will see the 7th line from the bottom.
However I have just kept it as a cout.

NI_SH · November 4, 2019, 1:25pm

Python3, simply k - min

t = int(input())
while t > 0:
n,k = list(map(int,input().split()))
arr = list(map(int,input().split()))
print(k - min(arr))
t -= 1

dEnOmInAtOr · October 20, 2019, 7:31pm

t = int(input())
while(t):
    n,k = list(map(int, input().split()))
    l = list(map(int, input().split()))
    if(k>min(l)):
        print(k-min(l))
    else:
        print(0)
    t-=1

dEnOmInAtOr · October 21, 2019, 7:02am

Problem 2:
Given an array find a pair(a,b) such that a+b=X
Example:
input:
7 11
1 2 10 6 9 11 5
output: 6, 5

description:
input: the first line contains 2 numbers n, k where n is the length of the array and 11 is X, next line contains an array of length n.
output: print two number from array which sum to X (you can have multiple answers and also order invariant. i.e you can print wither 5,6 or 6,5)

Level: Easy
Asked By: Google
Prefered Time Complexity: O(N)

Hello @Summer_Jance

map in python are not hashmaps, it is a function that applies a function to an iterable.
reference: https://www.programiz.com/python-programming/methods/built-in/map

Time Complexity Analysis of yesterdays problem:
O(N) for finding minimum element using python min function, rest are just constant operations.

Summer_Jance · October 21, 2019, 7:53am

Problem 2

Is K an X?
not sure of O(N) soln but O(NlogN) is quite easy to find.

Darklooter · October 21, 2019, 8:49am

Is that anyhow related to the one in google youtube video?

Darklooter · October 21, 2019, 8:55am

Hi @dEnOmInAtOr is the question correct ?
As per your question “input: first line contains 2 numbers n, k where n is length of array and 11 is X, next line contains an array of length n.”
So as per your Input:
7 11
For the given array {1 2 10 6 9 11 5}
The output should be : 6,5 or 1,10(As x=11)
Also kindly try to add a problem number with each question like my first question has problem 1 code you can rename it to problem 2 so it will be easy to sort answers based on problem codes.

Summer_Jance · October 21, 2019, 9:16am

yes , you’re right
X is K
and
6,5 or 1,10 one of the output should be printed.

dEnOmInAtOr · October 21, 2019, 1:56pm

Sorry, Guys,
Modified the Question accordingly.

@Darklooter, I’m not sure which video it is.

By the way, Total Solution.

First, you have to traverse through the array and save all the elements in the hashmap.
Now, you have to traverse through the array again and check if the difference between sum and the current element is present in the hash(i.e., K - curr_ele is present or not in hashmap); if present, that means you have the other element also which sums to K.

C++ solution:

#include<bits/stdc++.h>
using namespace std;

int findPairSum(int *arr, int size, int sum){
    map <int, int> hash;
    for(int i=0;i<size;i++){
        if(hash.find(arr[i])==hash.end())
            hash.insert({arr[i],1});
    }
    for(int i=0;i<size;i++){
        int a = arr[i];
        int b = sum-a;
        if(hash.find(b)!=hash.end()){
            cout << "Sum forming pairs are, " << a << " " <<  b ;
            return 0;
        }
    }
    return -1;
}

int main(){
    int k, n;
    cin >> n >> k;
    int arr[n];
    for(int i=0;i<n;i++) cin >> arr[i];
    if(findPairSum(arr, sizeof(arr)/sizeof(arr[0]), k)==-1) cout << "No such pairs!";
    return 0;
}

Python solution:
Pointer: Hashmaps are called dictionaries in python.

n, k = list(map(int, input().split()))
arr = list(map(int, input().split()))    
myhash = dict()
    f=0
    for ele in arr:
        myhash[ele]=1
    for ele in arr:
        if(k-ele in myhash):
            print(ele, k-ele)
            break
            f = 1
    if(f==0):
        print("No pair found!")

Time complexity: O(N)
Space complexity: O(N)

Tips:

If you don’t know what hashmaps are, learn them ASAP. Because learning hashmaps will help you in any coding problem to advance from O(N^2) or O(NlogN) to O(N) quickly but increases space complexity
Please note that time and space complexity go hand in hand. If you want to decrease one, you have to increase the other. (Interviewers mostly care about optimizing time complexity unless asked for space)
And Hashmaps are amortized to time complexity of O(1) and most companies accept that hashmap run in O(1) even there are collisions. (This problem only arises if you are participating in CP challenges, you don’t need to worry about them in programming interviews)

Please correct me if I’m wrong anywhere, as this is the first time I am posting on any platform.

Summer_Jance · October 21, 2019, 2:03pm

okay this is O(N) solution at worst case

{Assuming the array starts from index 0 as first element }
let X2 be X- first element
for i=1 to N
if X2-arr[i] == 0
print X2,X-X2
break the loop
end if
end for

pseudocode
time complexity O(N) {traverse through all the elements}
space complexity O(N) {for array + overheads} + O(1) , {variables}

Darklooter · October 21, 2019, 10:11am

Here is my solution to problem 2.
However it is not in O(n):
Code

output:

Explanation:
We would have used vectors for this but for the sake of putting something new i used dynamic arrays . we all know in C++ you can initialize an array such that int arr[n], where n is a variable so, to fix this we have used a logic of dynamic arrays using pointers. you can understand this in the line 5 &6 of code given above.
Now, coming my approach for this problem. Consider the array above is sorted (if not then std::sort() ).

Now make a sum variable in starting such that sum=firstElement+lastElement, and left=a[0] and right =a[n-1].
now start a loop until the given sum is not equal to x.
if the sum in the sorted array is greater than the given value of X. decrease the current index from the right side of array and update the left & right variables accordingly.
if the sum in the sorted array is less than the given value of X. increment the index from the left side of array and update the left & right variables accordingly.
once x become equal to sum the loop will break and print left and right.

Point 3 & 4 are important.

I hope this helps, please feel free to correct if there is any mistake .

aaron_punch · October 21, 2019, 6:01pm

which Ide is this?

Darklooter · October 22, 2019, 12:25am

Not an IDE I have setup sublime for C++
You can search like how to setup sublime for c++ to get the exact steps.

Summer_Jance · October 21, 2019, 10:32am

for simplicity sake don’t post the soln , instead have a link called spoiler.
Pseudocode is much preferred.

Summer_Jance · October 21, 2019, 3:07pm

Problem 3:
Given an array find a pair(a,b) such that a+b close to X.
you can have multiple solution, print one solution…
Example:
input:
7 11
1 2 10 6 9 11 5
output: {1,9}

description:
input: the first line contains 2 numbers n, X where n is the length of the array and 11 is X, next line contains an array of length n.
output: print two number from array whose sum is close to X (you can have multiple answers and also order invariant. )

Level: Not too Easy
Prefered Time Complexity: O(N)

Friendly Websites

Post Only Coding Problems & Solutions Here | All Coding Guru's Dig In

ALL CODING PROBLEMS & SOLUTION PLATFORM UNDER ONE ROOF!

Posting Rules:

HAPPY LEARNING! LET’S GET STARTED!