Amit_Badshah's blog

By Amit_Badshah, history, 5 days ago, In English,

https://leetcode.com/problems/zuma-game/description/

Need help in this problem,Unable to understand...

Read more »

 
 
 
 
  • Vote: I like it  
  • -1
  • Vote: I do not like it  

By Amit_Badshah, history, 8 days ago, In English,

http://poj.org/problem?id=2385

need help in this problem.I am able to solve the problem by heap.But Unable by Dynamic Programming

Read more »

 
 
 
 
  • Vote: I like it  
  • -7
  • Vote: I do not like it  

By Amit_Badshah, history, 12 days ago, In English,
Tags #dp
 
 
 
 

By Amit_Badshah, history, 5 weeks ago, In English,

An array contains both positive and negative numbers in random order. Rearrange the array elements so that positive and negative numbers are placed alternatively. Number of positive and negative numbers need not be equal. If there are more positive numbers they appear at the end of the array. If there are more negative numbers, they too appear in the end of the array.

For example, if the input array is [-1, 2, -3, 4, 5, 6, -7, 8, 9], then the output should be [2,-1,4,-3,5,-7,6,8,9]

array size < 10^3

Read more »

 
 
 
 
  • Vote: I like it  
  • -13
  • Vote: I do not like it  

By Amit_Badshah, history, 6 weeks ago, In English,

There are n-pairs and therefore 2n people. everyone has one unique number ranging from 1 to 2n. All these 2n persons are arranged in random fashion in an Array of size 2n. We are also given who is partner of whom. Find the minimum number of swaps required to arrange these pairs such that all pairs become adjacent to each other.

n<10^3 arr.size<10^3

Input: n = 3

pairs[] = {1->3, 2->6, 4->5} // 1 is partner of 3 and so on

arr[] = {3, 5, 6, 4, 1, 2}

Output: 2

We can get {3, 1, 5, 4, 6, 2} by swapping 5 & 6, and 6 & 1

(Google Interview)

Read more »

 
 
 
 
  • Vote: I like it  
  • +4
  • Vote: I do not like it  

By Amit_Badshah, history, 6 weeks ago, In English,

Minimum operations required to remove an array Given an array of N integers where N is even. There are two kinds of operations allowed on the array.

  1. Increase the value of any element A[i] by 1.
  2. If two adjacent elements in the array are consecutive prime number, delete both the element. That is, A[i] is a prime number and A[i+1] is the next prime number.

The task is to find the minimum number of operation required to remove all the element of the array.

size of array 10^5

size of element 10^3

Examples:

Input : arr[] = { 1, 2, 4, 3 } Output : 5

Minimum 5 operation are required.

  1. Increase the 2nd element by 1 { 1, 2, 4, 3 } -> { 1, 3, 4, 3 }

  2. Increase the 3rd element by 1 { 1, 3, 4, 3 } -> { 1, 3, 5, 3 }

  3. Delete the 2nd and 3rd element { 1, 3, 5, 3 } -> { 1, 3 }

  4. Increase the 1st element by 1 { 1, 3 } -> { 2, 3 }

  5. Delete the 1st and 2nd element { 2, 3 } -> { }

Input : arr[] = {10, 12} Output : 3

Read more »

 
 
 
 
  • Vote: I like it  
  • +19
  • Vote: I do not like it  

By Amit_Badshah, history, 6 weeks ago, In English,

Given an array of n integers. Find the maximum value of arr[i] mod arr[j] where arr[i] >= arr[j] and 1 <= i, j <= n

where arr.size<10^3 n<10^3

Input: arr[] = {3, 4, 7}

Output: 3

Explanation:

There are 3 pairs which satisfies arr[i] >= arr[j] are:-

4, 3 => 4 % 3 = 1

7, 3 => 7 % 3 = 1

7, 4 => 7 % 4 = 3

Hence Maximum value among all is 3.

Input: arr[] = {3, 7, 4, 11}

Output: 4

Input: arr[] = {4, 4, 4}

Output: 0

Read more »

 
 
 
 
  • Vote: I like it  
  • -36
  • Vote: I do not like it  

By Amit_Badshah, history, 6 weeks ago, In English,

Given two arrays A[] and B[], write an efficient code to determine if every element of B[] is divisible by at least 1 element of A[]. Display those elements of B[], which are not divisible by any of the element in A[].

Examples:

Input : A[] = {100, 200, 400, 100, 600}

B[] = {45, 90, 48, 1000, 3000}

Output : 45, 90, 48

The output elements are those that are

not divisible by any element of A[].

n<10^5 arr.size<10^5

Read more »

 
 
 
 
  • Vote: I like it  
  • -1
  • Vote: I do not like it  

By Amit_Badshah, history, 6 weeks ago, In English,

Given a non negative array, find the number of subsequences having product smaller than K.

k<10^2 arr.size<10^3

Examples:

Input : [1, 2, 3, 4]

k = 10

Output :11

The subsequences are {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {1, 2, 3}, {1, 2, 4}

Input : [4, 8, 7, 2]

k = 50

Output : 9

Read more »

 
 
 
 
  • Vote: I like it  
  • +6
  • Vote: I do not like it  

By Amit_Badshah, history, 6 weeks ago, In English,

Given an array with non negative numbers, divide the array into two parts such that the average of both the parts is equal. Return both parts (If exist).

If there is no solution. return an empty list.

Example:

Input:

[1 7 15 29 11 9]

Output:

[9 15] [1 7 11 29]

The average of part is (15+9)/2 = 12,

average of second part elements is (1 + 7 + 11 + 29) / 4 = 12

arr.size<10^3

Read more »

 
 
 
 
  • Vote: I like it  
  • -18
  • Vote: I do not like it  

By Amit_Badshah, history, 6 weeks ago, In English,

Given N point on a 2D plane as pair of (x, y) co-ordinates, we need to find maximum number of point which lie on the same line.

Examples:

Input : points[] = {-1, 1}, {0, 0}, {1, 1}, {2, 2}, {3, 3}, {3, 4}

Output : 4

Then maximum number of point which lie on same

line are 4, those point are {0, 0}, {1, 1}, {2, 2}, {3, 3}

where arr.size<10^3

Read more »

 
 
 
 
  • Vote: I like it  
  • +7
  • Vote: I do not like it  

By Amit_Badshah, history, 7 weeks ago, In English,

In a given array nums of positive integers, find three non-overlapping subarrays with maximum sum.

Each subarray will be of size k, and we want to maximize the sum of all 3*k entries.

Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

Example:

Input: [1,2,1,2,6,7,5,1], 2

Output: [0, 3, 5]

Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].

We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.

Note:

nums.length will be between 1 and 20000.

nums[i] will be between 1 and 65535.

k will be between 1 and floor(nums.length / 3).

Read more »

 
 
 
 

By Amit_Badshah, history, 7 weeks ago, In English,

We have N (where N > 2) stones of various heights laid out in a row. Task is to make a pyramid from given array of stones. In a pyramid, height of the stones start from 1, increase by 1, until it reaches some value x, then decreases by 1 until it reaches 1 again i.e. the stones should be 1, 2, 3, 4…x – 1, x, x – 1, x – 2 … 1. All other stones not part of the pyramid should have a height 0. We cannot move any of the stones from their current position, however, by paying a fee of 1, we can reduce the heights of the stones. We wish to minimize the cost of building a pyramid. Output the minimum cost to build this pyramid.

N<10^3 height<10^4

Examples:

Input : 1 2 3 4 2 1

Output : 4

The best pyramid that can be formed in this case is:

1 2 3 2 1 0

The cost is thus:

(4 — 2) + (2 — 1) + (1 — 0) = 4

Input : 1 5 2

Output : 4

We make a pyramid 1 2 1

Input : 1 2 1

Output : 0

We already have a pyramid, we do not need to do any

further construction.

Read more »

 
 
 
 

By Amit_Badshah, history, 2 months ago, In English,

Given an integer n > 0, which denotes the number of digits, the task to find total number of n-digit positive integers which are non-decreasing in nature.

A non-decreasing integer is a one in which all the digits from left to right are in non-decreasing form. ex: 1234, 1135, ..etc.

Note :Leading zeros also count in non-decreasing integers such as 0000, 0001, 0023, etc are also non-decreasing integers of 4-digits.

Examples:

Input : n = 1

Output : 10

Numbers are 0, 1, 2, ...9.

Input : n = 2

Output : 55

Input : n = 4

Output : 715

where n<10^3

Read more »

 
 
 
 

By Amit_Badshah, history, 2 months ago, In English,

Given an array of n integers, count all different triplets whose sum is equal to the perfect cube i.e, for any i, j, k(i < j < k) satisfying the condition that a[i] + a[j] + a[j] = X3 where X is any integer. 3 ≤ n ≤ 1000, 1 ≤ a[i, j, k] ≤ 5000

Input:

N = 5

2 5 1 20 6

Output:

3

Explanation:

There are only 3 triplets whose total sum is a perfect cube.

Indices Values SUM

0 1 2 2 5 1 8

0 1 3 2 5 20 27

2 3 4 1 20 6 27

Since 8 and 27 are prefect cube of 2 and 3.

Read more »

 
 
 
 
  • Vote: I like it  
  • -12
  • Vote: I do not like it  

By Amit_Badshah, history, 2 months ago, In English,

Given two positive integer n and n. The task is to find the number of arrays of size n that can be formed such that :

Each element is in range [1, m]

All adjacent element are such that one of them divide the another i.e element Ai divides Ai + 1 or Ai + 1 divides Ai + 2.

Examples:

Input : n = 3, m = 3.

Output : 17

{1,1,1}, {1,1,2}, {1,1,3}, {1,2,1},

{1,2,2}, {1,3,1}, {1,3,3}, {2,1,1},

{2,1,2}, {2,1,3}, {2,2,1}, {2,2,2},

{3,1,1}, {3,1,2}, {3,1,3}, {3,3,1},

{3,3,3} are possible arrays.

Input : n = 1, m = 10.

Output : 10

can any one help me in this interesting dp problem?

Read more »

 
 
 
 
  • Vote: I like it  
  • +11
  • Vote: I do not like it  

By Amit_Badshah, history, 2 months ago, In English,

Actually I am looking for a good problemset on codeforces.If any user while solving problems keep their information please mention your list of problems according to topics.Basically advance data structure problems would be a big plus..Thanks in advance.

Read more »

 
 
 
 
  • Vote: I like it  
  • -1
  • Vote: I do not like it  

By Amit_Badshah, history, 2 months ago, In English,

Given an array, we need to find two subarrays with a specific length K such that sum of these subarrays is maximum among

all possible choices of subarrays.

arr size <10^5

n<10^3

Examples:

Input : arr[] = [2, 5, 1, 2, 7, 3, 0]

K = 2

Output : 2 5

7 3

We can choose two arrays of maximum sum

as [2, 5] and [7, 3], the sum of these two

subarrays is maximum among all possible

choices of subarrays of length 2.

Input : arr[] = {10, 1, 3, 15, 30, 40, 4, 50, 2, 1}

K = 3

Output : 3 15 30

40 4 50

Read more »

 
 
 
 
  • Vote: I like it  
  • -13
  • Vote: I do not like it  

By Amit_Badshah, history, 2 months ago, In English,

Given an array arr[] of n elements,

update all elements of given array to some minimum value x i.e, arr[i] = x (0 <= i < n),

such that product of all elements of this new array is strictly greater than the product of

all elements of the initial array, where 1 <= arr[i] <= 10^10 and 1 <= n <= 10^5

Input : arr[] = [4, 2, 1, 10, 6]

Output : 4

4 is the smallest value such that

4 * 4 * 4 * 4 * 4 > 4 * 2 * 1 * 10 * 6

Input : arr[] = [100, 150, 10000, 123458, 90980454]

Output : 17592

Expected time Complexity:O(N)

Read more »

 
 
 
 
  • Vote: I like it  
  • -16
  • Vote: I do not like it  

By Amit_Badshah, history, 2 months ago, In English,

Given an array of integers. Find the total number of subarrays whose product of all elements doesn’t contain repeating prime

factor in prime decomposition of resulting number.

Input: 2 3 9

Output: 3

Explanation:

Total sub-array are:-

{2}, {3}, {9}, {2, 3}, {3, 9}, {2, 3, 9}

Subarray which violets the property are:-

{9} -> {3 * 3}, Since 3 is a repeating prime

factor in prime decomposition of 9

{3, 9} -> {3 * 3 * 3}, 3 is a repeating prime

factor in prime decomposition of 27

{2, 3, 9} -> {2 * 3 * 3 * 3}, 3 is repeating

prime factor in prime decomposition 

         of 54

Hence total subarray remains which satisfies our

condition are 3.

Input: 2, 3, 5, 15, 7, 2 Output: 12

Read more »

 
 
 
 
  • Vote: I like it  
  • -5
  • Vote: I do not like it  

By Amit_Badshah, history, 2 months ago, In English,

Given an array of N positive integers. Count the number of pairs whose sum exists in the given array. While repeating pairs will not be counted again. And we can’t make a pair using same position element. Eg : (2, 1) and (1, 2) will be considered as only one pair.

I was able to solve problem in O(n2).I want a solution less then this.

Please read all examples carefully.

Examples:

Input : arr[] = {1, 2, 3, 5, 10}

Output : 2

Explanation : Here there are two such pairs:

(1 + 2) = 3, (2 + 3) = 5.

Note : Here we can't take pair (5, 5) as

we can see 5 is not coming twice

Input : arr[] = {1, 5, 6, 4, -1, 5}

Output : 4

Explanation : (1 + 5) = 6, (1 + 4) = 5,

(5 + -1) = 4, (6 + -1) = 5

Note : Here (1, 5) comes twice will be

considered as only one pair.

Input : arr[] = {5, 5, 5, 5, 10}

Output : 1

Explanation : (5 + 5) = 10

Note : Here (5, 5) comes twice will be

considered as only one pair.

Read more »

 
 
 
 
  • Vote: I like it  
  • -12
  • Vote: I do not like it  

By Amit_Badshah, history, 2 months ago, In English,

Given an unsorted array A and a number k, find the maximum sum sub string in the array such that its sum is divisible by k.

eg. k=3 arr[1,2,3,-3,-4,1,0,-2,5,4,5]

ans=12 sum from [-2,5,4,5]

Read more »

 
 
 
 
  • Vote: I like it  
  • -16
  • Vote: I do not like it  

By Amit_Badshah, history, 2 months ago, In English,

Suppose a chemical Formula is given C6H2(Cl3(OH2)3)3

Print: C-6 H-20 O-9 Cl-9 (Print the number of atoms of each element in a compound)

Read more »

 
 
 
 
  • Vote: I like it  
  • -8
  • Vote: I do not like it  

By Amit_Badshah, history, 2 months ago, In English,

My approach->

create a hash map that contains the value of the ending index of the previous sequence.

For example

when we get 1,3,5 the hash map is

1 0

3 1

5 2

key is the number and the value is the index where it occurs.

when we get 4, we have to check for the index of 3 and 5. (One above and one below)

the value at 3 is 1 and 4’s index is 3, so they can’t be paired.

We then check for 5. 5’s index is 2 and 4’s is 3, since they are together, they can be paired.

1 0

3 1

5 2-3

4 2-3

and then we check for 3 again, 3’s index is 1 and 4’s index is 2-3, so they can match

1 0

3 1-3

5 1-3

4 1-3

We go on.

Then they alterd the question like

modified more to include distributed systems in it. And asked me if there were several systems which received the input in round robin manner, how would I implement the above algorithms.

Read more »

 
 
 
 
  • Vote: I like it  
  • -36
  • Vote: I do not like it  

By Amit_Badshah, history, 3 months ago, In English,

Given a binary tree return a matrix where mat(i,j) is 1 when i is an ancestor of j. only one traversal required and no extra space required,

Read more »

 
 
 
 
  • Vote: I like it  
  • -13
  • Vote: I do not like it