Accenture ADVANCED CODING

1. For hiring a car, a travel agency charges R1 rupees per hour for the first N hours and then R2 rupees
per hour. Given the total time of travel in minutes is X. The task is to find the total traveling cost in
rupees.
Note: While converting minutes into hours, ceiling value should be considered as the total number of
hours.
For example: If the total travelling time is 90 minutes,
i.e. 1.5 hours, it must be considered as 2 hours.
Input Output Explanation
20 ---Value of R1
Total travelling hours = 300/60 = 5 hours
4 --- Value of N in hours
Rupees 20/hours for first 4 hours = 20 * 4 = 80 rupees
40 --- Value of R2 120
Rupees 40/hours in 5th hour = 40 * 1 = 40 rupees
300 --- Value of X in
Hence, the total travelling cost = 80 + 40 = 120 rupees
minutes
Total travelling hours = 500/60 = 8.33, Ceiling value of 8.33
30 --- Value of R1
= 9 hours
5 --- Value of N in hours.
290 Rupees 30/hours for first 5th hours = 30 * 5 = 150 rupees
35 --- Value of R2
Rupees 35/hours in 5th hour = 35 * 4 = 140 rupees
500 -- Value of X in minutes
Hence, the total travelling cost = 150 + 140 = 290 rupees
30--- Value of R1
Total travelling hours = 3/60 = 0.05, Ceiling value of 0.05 = 1
10--- Value of N in hours
30 hour
35 ---- Value of R2
Rupees 30/hour for first 10 hours = 30 * 1 = 30 rupees
5 --- Value of X in minutes

Constraints:
1 < R1 < R32< 100
1 < = N < = 10
1 < = X < 10000
Code Solution in Python
r1 = int(input())
n = int(input())
r2 = int(input())
k = int(input())
hr = (k+59)//60
of(hr>n);
focus = n*r1+(hr-n)*r2
else:
focus = n*r1
print(focus)

Page 1 of 66
Accenture ADVANCED CODING

Code Solution in Java

Import [Link],*;
class Main
{
public static void main(String args[])
{
Scanner sc=new Scanner([Link]);
int r1=[Link]();
int n=[Link]();
int r2=[Link]();
int k=[Link]();
int focus, hr;
hr = (k+59)/60;
if(hr> n)
focus = n*r1+(hr-n)*r2
else:
focus = n*r1
[Link](focus);
}
}
Code Solution in CPP
#include<iostream>
using namespace std;
int main()
{
Int r1, n, r2, k, focus, hr;
cin>>r1>>n>>r2>>k;
hr = (k+59)/60;
if(hr> n)
{
Focus = n*r1+(hr-n)*r2;
}
else
{
focus = n*r1;
}
cout<<foucus;
return 0;
}

Page 2 of 66
Accenture ADVANCED CODING

Code Solution in C
#include<stdio.h>
int main()
{
int r1, n, r2, k, focus, hr;
scanf(“%d%d%d%d”, &r1, &n, &r2, &k);
hr= (k+59)/60;
if(hr> n)
{
focus = n*r1+(hr-n)*r2;
}
else
{
focus = n*r1;
}
printf(“%d”, focus);
return 0;
}

2. There is a bag with three types of gemstones: Ruby of type R, Garnet of type g, and Topaz of type T.
Write a program to find the total number of possible arrangements to make a series of gemstones
where no two gemstones of the same type are adjacent to each other.
Input Output Explanation
1-Count of R i.e. Ruby
1-Count of G i.e. Garnet 2 Arrangements are RG and GR.
0-Count of T i.e.
1-Count of R i.e. Ruby
Arrangements are RGTR, GRTR, RGRT, RTGR, RTRG AND
1-Count of G i.e .Garnet 6
TRGR
1-Count of T i.e. Topaz

Code Solution in CPP

#include<bits/stdc++.h>
Using namespace std;
int countWays(int p, int q, int r, int last)
{
if (p<0 || q<0 || r<0)
return 0;
if (p==1 && q==0&& r==0 && last==0)
return 1;

Page 3 of 66
Accenture ADVANCED CODING

if (p==0&& q==1&& r==0 && last==1)

return 1;
if (p==0&& q==0 && r==1&& last==2)
return 1;
if (last==0)
return countWays (p-1,q,r,1) + countWays(p-1,q,r,2);
if (last==1)
return countWays (p,q-1,r,0) + countWays(p,q-1,r,2);
if (last==2)
return countWays (p,q,r-1,0) + countWays(p,q,r-1,1);
}
int faceprep(int p, int q, int r)
{
return countWays (p, q, r, 0) +
countWays (p, q, r, 1) +
countWays (p, q, r, 2) ;
}
int main()
{
int p,q,r;
cin>>p>>q>>r;
printf(“%d”, faceprep(p, q, r));
return 0;
}
Code Solution in C
#include<stdio.h>
int countWays(int p, int q, int r, int last)
{
if (p<0 || q<0 || r<0)
return 0;
if (p==1 && q==0 && r==0 && last==0)
return 1;
if (p==0&& q==1&& r==0 && last==1)
return 1;
if (p==0&& q==0 && r==1&& last==2)
return 1;
if (last==0)
return countWays (p-1,q,r,1) + countWays(p-1,q,r,2);
if (last==1)

Page 4 of 66
Accenture ADVANCED CODING

return countWays (p,q-1,r,0) + countWays(p,q-1,r,2);

if (last==2)
return countWays (p,q,r-1,0) + countWays(p,q,r-1,1);
}
int faceprep(int p, int q, int r)
{
return countWays (p, q, r, 0) +countWays (p, q, r, 1) +countWays (p, q, r, 2) ;
}
int main()
{
int p,q,r;
scanf(“%d%d%d”, &p, &q, &r);
printf(“%d”, faceprep(p, q, r));
return 0;
}
Code Solution in Python
def countWays(p,q,r,last);
if (p<0 or q<0 or r<0)
return 0;
if (p==1 and q==0 and r==0 and last==0)
return 1;
if (p==0 and q==1 and r==0 and last==1)
return 1;
if (p==0 and q==0 and r==1 and last==2)
return 1;
if (last==0);
return countWays (p-1,q,r,1) + countWays(p-1,q,r,2);
if (last==1);
return countWays (p,q-1,r,0) + countWays(p,q-1,r,2);
if (last==2);
return countWays (p,q,r-1,0) + countWays(p,q,r-1,1);
def faceprep(p, q, r);
return countWays (p, q, r, 0) + countWays (p, q, r, 1) + countWays (p, q, r, 2) ;
p = int (input())
q = int (input())
r = int (input())
print(faceprep(p, q, r))

Code Solution in Java

Page 5 of 66
Accenture ADVANCED CODING

import [Link].*;
class Main{\
static int countWays(int p, int q, int r, int last)
{
if (p<0 || q<0 || r<0)
return 0;
if (p==1 && q==0 && r==0 && last==0)
return 1;
if (p==0 && q==1 && r==0 && last==1)
return 1;
if (p==0 && q==0 && r==1 && last==2)
return 1;
if (last==0)
return countWays (p-1,q,r,1) +
countWays(p-1,q,r,2);
if (last==1)
return countWays (p,q-1,r,0) +
countWays(p,q-1,r,2);
if (last==2)
return countWays (p,q,r-1,0) +
countWays(p,q,r-1,1);
return 0;
}
static int faceprep(int p, int q, int r){
return countWays (p, q, r, 0) +
countWays (p, q, r, 1) +
countWays (p, q, r, 2) ;
}
public static void main(String[] args)
{
Scanner sc=new Scanner([Link]);
int p=[Link]();
int q=[Link]();
int r=[Link]();
[Link](faceprep(p, q, r));
}
}
3. Given an array Arr[] of N integer numbers. The task is to rewrite the array by putting all multiples of
10 at the end of the given array.

Page 6 of 66
Accenture ADVANCED CODING

Note: The order of the numbers which are not multiples of 10 should remain unaltered, and similarly,
the order of all multiples of 10 should be unaltered.
For e.g.
Suppose N = 9 and Arr[]={10, 12, 5, 40, 30, 7, 50, 9, 10}
You have to push all multiple of 10 at the end of the Arr[]
Hence, the output is 12 5 7 9 10 40 30 50 10.

Input Output
9 …. Value of N
12 5 7 9 10 40 30 50 10
10 12 5 40 30 7 50 9 10 … Elements of Arr[]
9 ….. Value of N
21 5 6 3 7 11 89 100 10
100 21 5 6 3 7 11 89 10…. Elements of Arr[]

Constraints:
1 < N < = 100
.100 < = Arr[i] < = 100
Input Format for Testing:
1. First input line: Accept a single positive integer value for N representing the size of Arr[].
2. Second Input line: Accept N number of integer values separated by a new line.
Output Format for Testing:
1. The output must be N integer numbers separated by a single space character (See the output
format in examples).
2. Additional messages in the output will result in the failure of test cases.
Code Solution in Python
n = int(input())
l = list(map(int, input(). split()))
m = []
n = []
for i in l;
if i%10==0 and i!=0;
[Link](i)
else:
[Link](i)
print(*m+n)
Code Solution in Java
import [Link].*;
class Main
{
public static void main (String[] args) {

Page 7 of 66
Accenture ADVANCED CODING

Scanner sc=new Scanner ([Link]);

int n=[Link]();
int arr[]=new int[n];
int i;
for(i=0; i<n;i++)
arr[i]=[Link]();
for(i=0; i<n;i++)
if(arr[i]%10!=0)
[Link](“%d”, arr[i]);
for(i=0;i<n;i++)
if(arr[i]%10==0)
[Link](“%d”, arr[i]);
}
}
Code Solution in C++
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
int arr[n];
int i;
for (i=0; i<n; i++)
cin>>arr[i];
for(i=0; i<n:i++)
if(arr[i]%10!=0)
count<<arr[i]<<” “;
for(i=0; i<n; i++)
if(arr[i]%10==0)
cout<<arr[i]<<” “;
}
Code Solution in C
#include <stdio.h>
int main()
{
int m, i, a[10];
scanf(“%d”, &n);
for(I = 0; i<n; i++)

Page 8 of 66
Accenture ADVANCED CODING

}
for(a[i]%10 !=0)
{
printf(“%d”, a[i]);
}
}
for(I = 0; i<n; i++)
{
if(a[i]%10==0)
{
printf(“%d”, a[i]);
}
}
return 0;
}
4. Given an array Arr[N] of N integers and a positive integer K. The task is to divide the array into two
sub-arrays from right after the Kth position and slide the left sub-array of K elements to the end.

Input Output Explanation

5 -- Value of N Arr[] = {10,20,30,40,50} and K=2 (2nd position)
{10, 20, 30, 40, 50} -- Divide array from after 2nd position and add left
30 40 50 10 20
Elements of Arr [] sub-array {10,20} to the end.
2 -- Value of K So the output is 30 40 50 10 20
4 -- Value of N Arr[] = {10, 20, 30, 40} and K=1 (1st position)
{10, 20, 30, 40} -- Elements Divide array from after 1st position and add left sub-
20 30 40 10
of Arr [] array {10} to the end.
1 -- Value of K So the output is 20 30 40 10
4 -- Value of N Arr[] = {10, 20, 30, 40} and K=3 (3rd position)
{10, 20, 30, 40} -- Elements Divide array from after 3rd position and add left sub-
40 10 20 30
of Arr[] array {10, 20, 30} to the end.
3 -- Value of K So the output is 40 10 20 30

Constraints
1<N<=100
-100<=Arr[i]<=100
1<=K<N
Code Solution in Python
def rightRotateByOne(A):
last = A[-1]

Page 9 of 66
Accenture ADVANCED CODING

for iin reversed(range(len(A) – 1)):

A[i+ 1] = A[i]
A[0] = last
def rightRotate(A, k):
for i in range (k):
rightRotateByOne(A)
n=int(input())
A=[]
for i in range(n):
r=int(input())
[Link](r)
k = int(input())
rightRotate(A, k)
for i in range(n):
print (A[i], end=” “)
Code Solution in Java
import [Link].*;
public class Main
{
public static void Rotateby(int arr[], int n)
{
int x = arr[n-1], i;
for (i=n-1; i>0; i--)
arr[i] = arr[I – 1];
arr[0] = x;
}
public static void Rotate (int arr[], int d, int n)
{
for (int i = 0; I < d; i++)
Rotateby(arr, n);
}
public stativcoidprintArray(int arr[], int n)
{
for (int i = 0; i< n; i++)
[Link](“%d”, arr[i]);
}
public static void main(String args[])
{
Scanner sc=new Scanner([Link]);

Page 10 of 66
Accenture ADVANCED CODING

int I;
int n=[Link]();
int arr[]=new int[n];
for (i = 0; i<n;i++)
arr[i]=[Link]();
int k=[Link]();
Rotate(arr, k, n);
printArray(arr, n);
}
}
Code Solution in C++
#include <bits/stdc++.h>
using namespace std;
void Rotateby(int arr[], int n)
{
int x = arr[n-1], i;
for (i = n – 1; i> 0; i --)
arr[i] = arr[i – 1];
arr[0] = x;
}
void Rotate(int arr[], int d, int n)
{
for (int i = 0; I < d; i++)
Rotateby(arr, n);
}
void printArray(int arr[], int n)
{
for (int i = 0; i< n; i++)
cout<<arr[i]<<” “;
}
int main()
{
int arr[10], i;
int n,k;
cin>>n;
for(i=0; i<n;i++)
cin>>arr[i];
cin>>k;
Rotate(arr,k,n);
printArray(arr, n);
return 0;
}
Code Solution in C

Page 11 of 66
Accenture ADVANCED CODING

#include<stdio.h>
void Rotateby(int arr[], int n)
{
int x = arr[n – 1], i;
for (i = n – 1; i> 0; i --)
arr[i] = arr[I – 1];
arr[0] = x;
}
void Rotate(int arr[], int d, int n)
{
for (int i = 0; i<d; i++)
Rotateby(arr, n);
}
void printArray(int arr[], int n)
{
for (int i = 0; i< n; i++)
printf(“%d”, arr[i]);
}
int main()
{
int arr[10], i;
int n, k;
scanf(“%d”, &n);
for(i = 0; i< n; i++)
scanf(“%d”, &k);
Rotate(arr, k, n);
printArray(arr, n);
return 0;
{
5. Given two non-negative integers n1 and n2, where n1 <n2. The task is to find the total number of
integers in the range interval [n1, n2] [both inclusive] which have no repeated digits.
For e.g.
Suppose n1 = 11 and n2 = 15.
There is the number 11, which has repeated digits, but 12, 13, 14, and 15 have no repeated digits. So,
the output is 4.

Input Output
11 -- Value of n1
4
15 -- Value of n2
101 -- Value of n1
72
200 -- Value of n2
Code Solution in Python
def repeated_digit(n);

Page 12 of 66
Accenture ADVANCED CODING

a = []
while n ! = 0;
d = n%10
if d in a:
return 0
[Link](d)
n = n//10
return 1
def calculate (L, R):
answer = 0
for I in range(L, R + 1);
answer = answer + repeated_digit(i)
return answer
L=int(input())
R=int(input())
print (calculate(L, R))
Code Solution in Java
Import [Link].*;
class Main
{
static int repeated_digit(int n)
{
LinkedHashSet<Integer> S = new LinkedHashSet<>();
while (n !=0)
{
int d = n% 10;
if ([Link](d))
{
return 0;
}
[Link](d);
n = n/10;
}
return 1;
}
static int calculate(int L, int R)
{
int answer = 0;
for (int i = L; i< R + 1; ++i)
{
answer = answer + repeated_digit(i);
}
return answer;
}
public static void main([Link]);

Page 13 of 66
Accenture ADVANCED CODING

int L=[Link]();
int R=[Link]();
[Link](calculate(L, R));
}
}
Code Solution in C
#include<stdio.h>
#include<stdbool.h>
void printUnique (int 1, int r)
{
int count = 0;
for (int i=1; i<=r; i++)
{
int num = i;
bool visited[10] = {false};
while (num)
{
if (visited[num % 10])
break;
visited[num%10] = true;
num = num/10;
}
if(num == 0)
count++;
}
printf(“%d”, count);
}
int (main()
{
int 1, r;
scanf(“%d%d”, &1, &r);
printUnique(1, r);
return 0;
}
Code Solution in C++
#include<bits/stdc++.h>
using namespace std;
void printUnique(int1, int r)
{
int count = 0;
for(int i=1; i<r; i++)
{
int num = i;
bool visited[10] = {false};
while (num)

Page 14 of 66
Accenture ADVANCED CODING

{
if (visited[num % 10])
break;
visited[num%10] = true;
num = num/10;
}
if (num == 0)
count++;
}
cout<<count;
}
int main()
{
int 1, r;
cin>>1>>r;
printUnique(1, r);
return 0;
}
6. Given an array Arr[] of N integers and a positive integer K. The task is to cyclically rotate the array
clockwise by K.
Note: Keep the first position of the array unaltered.

Example Input Output Explanation

Arr[] = {10, 20, 30, 40, 50} and K =
5 -- Value of N 2 (Two cyclical rotations)
Example {10, 20, 30, 40, 50} -- Elements of After 1st rotation = {10, 50, 20, 30,
40 50 10 20 30
1 Arr[] 40}
2 -- Value of K After 2nd rotation = {10, 40, 50,
20, 30}
4 -- Value of N Arr[] = {10, 20, 30, 40} and K=1
Example {10, 20, 30, 40} -- Elements of (One cyclical rotation)
40 10 20 30
2 Arr[]
1 -- Value of K After 1st rotation = {10, 40, 20, 30}
Constraints
1 < N <=100
-100 <= Arr[i] <=100
1 <=K <=100
Input format for testing
The candidate should write the code to accept the inputs separated by a new line.
First Input: Accept a single positive integer value for N representing the size of Arr[]
Second Input: Accept N number of integer values separated by a new line, as elements of Arr[]

Page 15 of 66
Accenture ADVANCED CODING

Third input: Accept a single positive integer value for K representing the number of rotations.
Output format for testing
The output must be N integer numbers separated by a single space character.
Additional messages in the output will result in the failure of test cases.
Instructions
The system does not allow any kind of hard-coded input value/ values.
The written program code by the candidate will be verified against the input which are supplied from
the system.
Code Solution in Python
def rightRotateByOne(A)
last = A[-1]
for i in reversed(range(len(A) – 1)):
A[i + 1] = A[i]
A[0] = last
def rightRotate(A, k):
for i n range(k):
rightRotateByOne(A)
n=int(input())
A=[]
for i in range(n):
r=int(input())
[Link](r)
k = int(input())
rightRotate(A, k)
for i in range(n):
print(A[i], end= “ “)
Code Solution in Java
import [Link].*;
public class Main
{
public static void Rotateby(int arr[], int n)
}
int x = arr[n – 1], i;
for (i = n – 1;i>0; i--)
arr[i] = arr[i – 1];
arr[0] = x;
}
public static void Rotate(int arr[], int d, int n)
}
for (int i = 0; i< d; i++)
Rotateby(arr, n);
}
public static void printArray(int arr[], int n)
{

Page 16 of 66
Accenture ADVANCED CODING

for (int i = 0; i< n; i++)

[Link](“%d”, arr[i]);
}
public static void main([Link]);
int i;
int n=[Link]();
int arr[]=new int[n];
for(i=0; i<n;i++)
arr[i]=[Link]();
int k=[Link]();
Rotate(arr, k, n);
printArray(arr, n);
}
}
Code Solution C
#include<stdio.h>
void Rotateby(int arr[], int n)
{
int x = arr[n – 1], i;
arr[0] = x;
}
void Rotate(int arr[], int d, int n)
{
for (int i = 0; < d; i++)
Rotateby(arr, n);
}
void printArray(int arr[], int n)
{
for (int i = 0; i< n; i++)
printf(“%d”, arr[i]);
}
int main()
{
int arr[10], i;
int n, k;
scanf(“%d”, &n);
for(i = 0; i< n; i++)
scanf(“%d”, &arr[i];
scanf(“%d”, &k);
Rotate(arr, k, n);
printArray(arr, n);
return 0;
}
Code Solution C++
#include<bits/stdc++.h>

Page 17 of 66
Accenture ADVANCED CODING

using namespace std;

void Rotateby(int arr[], int n)
{
int x = arr[n – 1] i;
for (i = n – 1; i> 0; i --)
arr[i] =arr[i = 1];
arr[0] = x;
}
void Rotate(int arr[], int d, int n)
Rotateby (arr, n);
}
void printArray(int arr[], int n)
{
for (int i = 0; <n; i++)
cout<<arr[i] <<“ ”;
{
int main()
{
int arr[10], i;
int n, k;
cin>>arr[i];
for(i = 0; i<n;i++)
cin>>arr[i];
cin>>k;
Rotate(arr, k, n);
printArray(arr, n);
return 0;
}
7. Tiling Problem
Given a “2 x n” board and tiles of size “2 x 1”, count the number of ways to tile the given board using
the 2 x 1 tiles.
A tile can either be placed horizontally i.e., as a 1 x 2 tile or vertically i.e., as 2 x 1 tile.
Example:
Sample Input1:
4
Sample Output1:
3

Page 18 of 66
Accenture ADVANCED CODING

Example:
Sample Input1:
4
Sample Output1:
3
Explanation:
For a 2 x 4 board, there are 3 ways
All 4 vertical
All 4 horizontal
2 vertical and 2 horizontal
Sample Input2:
8
Sample Output1:
21

8. Problem Statement
You have been given a gold mine represented by a 2-d matrix of size ('N' * 'M') 'N' rows and 'M'
columns. Each field/cell in this mine contains a positive integer, the amount of gold in kgs.
Initially, the miner is at the first column but can be at any row.
He can move only right, right up, or right down. That is from a given cell and the miner can move to
the cell diagonally up towards the right or right or diagonally down towards the right.
Find out the maximum amount of gold he can collect.
Input Format:
The next '2' * 'T' lines represent the ‘T’ test cases.
The first line represents two single space-separated integers 'N' and 'M' denoting the size of the gold
mine.
The second line represents 'N' * 'M' space-separated integers representing the gold mine.
Output Format:
print an integer 'X' denoting the maximum amount of gold collected.
Note:
You are not required to print the output, it has already been taken care of. Just implement the
function.
Constraints:
1 <= N <= 100
1 <= M <= 100
0 <= gold at each cell <= 10^5
Sample Input 1:
4 4
10 33 13 15
22 21 4 1

Page 19 of 66
Accenture ADVANCED CODING

5023
0 6 14 2
Sample Output 1:
83
Explanation for the Sample Output 1:
Here miner starts from row 2 of the first column and collects gold of 22 kgs. Then he tries diagonally
up towards the right(33 kgs), straight right(21 kgs), and diagonally down towards the right(00 kgs)
and chooses the right upper diagonal cell.
Hence the total gold with miner is 22+33=55 kgs. Going forward, miner chose the straight right path
with 13 kgs and 15 kgs. Hence the maximum value of gold collected by the miner is 83 kgs.
There is no other path starting from any row of the first column, which gives the miner more gold
than 83kgs.
Sample Input 2:
33
134898756
Sample Output 2:
25

9. Mobile Numeric Keypad Problem

Given the mobile numeric keypad. You can only press buttons that are up, left, right or down to the
current button. You are not allowed to press bottom row corner buttons (i.e. * and # ).

Given a number N, find out the number of possible numbers of given length.
Examples:
For N=1, number of possible numbers would be 10 (0, 1, 2, 3, …., 9)
For N=2, number of possible numbers would be 36
Possible numbers: 00,08 11,12,14 22,21,23,25 and so on.
If we start with 0, valid numbers will be 00, 08 (count: 2)
If we start with 1, valid numbers will be 11, 12, 14 (count: 3)
If we start with 2, valid numbers will be 22, 21, 23,25 (count: 4)
If we start with 3, valid numbers will be 33, 32, 36 (count: 3)
If we start with 4, valid numbers will be 44,41,45,47 (count: 4)
If we start with 5, valid numbers will be 55,54,52,56,58 (count: 5)
………………………………

Page 20 of 66
Accenture ADVANCED CODING

………………………………
We need to print the count of possible numbers.

10. N-Queen problem

Problem Statement
You are given an integer N, and for a given N x N chessboard, find a way to place N queens such that
no queen can attack any other queen on the chessboard.
A queen can be killed when it lies in the same row, or same column, or the same diagonal of any of the
other queens. You have to print all such configurations.
Input Format:
The first and the only line of input contain an integer 'N' representing the size of the chessboard and
the number of queens.
Output Format:
Each line would be representing a single configuration.
Each configuration would contain N*N elements printed row-wise separated by spaces. The position
where we can place the queen will have the value 1 rest will have the value 0.
Constraints:
1 <= N <= 10
Sample Input 1:
4
Sample Output 1:
0100000110000010
0010100000010100
Explanation of The Sample Output1 1:
Output depicts two possible configurations of the chessboard for 4 queens.
The Chessboard matrix for the first configuration looks as follows:-
0010
1000
0001
0100
Queen contained cell is depicted by 1. As seen, No queen is in the same row, column or diagonal of the
other queens. Hence this is a valid configuration.
Sample Input 2:
3
Sample Output2:
Explanation of The Sample Input 2:
Since no possible configuration exists for 3 Queen’s. The Output remains Empty.

11. Find Smallest Integer

Page 21 of 66
Accenture ADVANCED CODING

You are given an array ARR consisting of N positive numbers and sorted in non-decreasing order,
your task is to find the smallest positive integer value that cannot be represented as a sum of
elements of any proper subset of the given array.
For Example:
For the given input array [1, 1, 3],
1 can be represented as the sum of elements of the subset [1],
2 can be represented as the sum of elements of subset [1, 1],
3 can be represented as the sum of elements of subset [3],
4 can be represented as the sum of elements of subset [1, 3],
5 can be represented as the sum of elements of subset [1, 1, 3]
So, the smallest positive integer value that cannot be represented as a sum of elements of any subset
of a given array is 6.
Input Format:
The first line contains an integer ‘N’ representing the size of the input array.
The second line contains elements of the array separated by a single space.
Output Format:
Prints a single integer which represents the smallest positive integer value that cannot be
represented as a sum of any subset of the given array.
Sample Input:
5
1 1 3 4 19
Sample Output:
10

12. Problem Statement

You are provided with a string ‘S’ which indicates the nested list.
For example: "[1, [2, 3], [4, [5, 6] ] ]".
Each number present in the list has some depth.
The depth of a particular number is the number of nested lists in which it is present.
Consider the previous example in which the number ‘1’ is at depth 1, numbers ‘2’, ‘3’, and ‘4’ are at
depth 2, and numbers ‘5’ and ‘6’ are at depth 3.
You have to find the goodness of the given string/nested list.
The goodness of a string is the sum of the product of depths and elements present in the string.
For Example:
S = "[1, [2, 3], [4, [5, 6] ] ]"
Total depth = 1*1 + 2*2 + 3*2 + 4*2 + 5*3 + 6*3 = 52
Note:
1. The given string may be empty.
2. The string will not contain any white spaces.
3. You have to take the modulo with 10 ^ 9 + 7 as the answer may be very large.

Page 22 of 66
Accenture ADVANCED CODING

Input Format:
The first represents a string ‘S’ which denotes the given nested list.
Output Format:
print a single line containing a single integer denoting the goodness of the given string.
Constraints:
1 <= |S| <= 100000
1 <= ES[i ] <= 10^5
Where “|S|” is the length of the given string, “ES[i ]” is the element/number stored in the string at the
“i-th” position.
Sample Input 1:
[1,[2,3],[4,[5,6]]]
Sample Output 1:
52
Explanation:-
Total depth = 1*1 + 2*2 + 3*2 + 4*2 + 5*3 + 6*3 = 52
Sample Input 2:
[1,[2,3],4,[15,10],34]
Sample Output 2:
99
Explanation For Sample Input 2:
Total depth = 1*1 + 2*2 + 3*2 + 4*1 + 15*2 + 10*2 + 34*1 = 99

13. Problem Statement:

Given 2 points ‘A’ and ’B’ that corresponds to the line ‘AB’ and ‘P’, ’Q’ that corresponds to line ‘PQ’ on
a 2D plane. Ninja wants to find the intersection point of the ‘AB’ and ‘PQ’ lines up to 6 decimal places.
If there is no such intersection point print -1.000000 -1.000000.
Note:
Lines ‘AB’ and ‘PQ’ are two different lines.
Input Format:
The first line represents 8 single space-separated integers ‘AX1’,’ AY1’, ’BX2’, ’BY2’, ’PX1’, ’PY1’, ’QX2’,
’QY2’ where ’AX1’ represents the ‘X’ coordinate of the point ‘A’ and ‘AY1’ represents the ‘Y’ coordinate
of the point ‘A’ and so on.
Output Format:
Print the ‘X’ and ‘Y’ coordinates of the point of intersection of the two lines ‘AB’ and ‘PQ’ up to 6
decimal places.
Sample Input 2:
23452617
Sample Output 2:
3.500000 4.500000
Explanation For Sample Output 2:

Page 23 of 66
Accenture ADVANCED CODING

The point of intersection of lines ‘AB’ and ‘PQ’ is (3.5, 4.5) and the output is printed up to 6 decimal
places. See the figure below:

14. Longest Common Subsequence

Problem Statement:-
Given two sequences, find the length of longest subsequence present in both of them.
A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.
For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”.
Sample Input:
ABCDGH
AEDFHR
Sample Output:
3
Explanation:-
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.

15. A Maze is given as N*N binary matrix of blocks where source block is the upper left most block i.e.,
maze[0][0] and destination block is lower rightmost block i.e., maze[N-1][N-1]. A rat starts from
source and has to reach the destination. The rat can move only in two directions: forward and
down.
In the maze matrix, 0 means the block is a dead end and 1 means the block can be used in the path
from source to destination. Note that this is a simple version of the typical Maze problem. For
example, a more complex version can be that the rat can move in 4 directions and a more complex
version can be with a limited number of moves.
Input :
{1, 0, 0, 0}
{1, 1, 0, 1}
{0, 1, 0, 0}
{1, 1, 1, 1}
Output:
{1, 0, 0, 0}

Page 24 of 66
Accenture ADVANCED CODING

{1, 1, 0, 0}
{0, 1, 0, 0}
{0, 1, 1, 1}

16. Check If Linked List Is Palindrome

You are given a Singly Linked List of integers. You have to find if the given linked list is palindrome or
not.
A List is a palindrome if it reads the same from the left to the right and from the right to the left.
For example, the lists (1 -> 2 -> 1), (3 -> 4 -> 4-> 3), and (1) are palindromes, while the lists (1 -> 2 ->
3) and (3 -> 4) are not.
Input Format:
The first line of input contains a single integer T, representing the number of test cases or queries to
be run.
Then the T test cases follow.
The first and only line of each test case contains the elements of the linked list separated by a single
space and terminated by -1. Hence, -1 would never be a list element.
Output Format:
For each test case, print “True” if the given linked list is a palindrome, else print “False”.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given
function.

17. Constellation
Three characters { #, *, . } represents a constellation of stars and galaxies in space. Each galaxy is
demarcated by # characters. There can be one or many stars in a given galaxy. Stars can only be in
the shape of vowels { A, E, I, O, U }. A collection of * in the shape of the vowels is a star. A star is
contained in a 3x3 block. Stars cannot be overlapping. The dot(.) character denotes empty space.
Given 3xN matrix comprising of { #, *, . } character, find the galaxy and stars within them.
Note: Please pay attention to how vowel A is denoted in a 3x3 block in the examples section below.
Constraints
3 <= N <= 10^5
Input
Input consists of a single integer N denoting the number of columns.
Output
The output contains vowels (stars) in order of their occurrence within the given galaxy. The galaxy
itself is represented by the # character.
Example 1
Input
18
*.*#***#***#***.*.
*.*#*.*#.*.#******

Page 25 of 66
Accenture ADVANCED CODING

***#***#***#****.*
Output
U#O#I#EA
Explanation
As it can be seen that the stars make the image of the alphabets U, O, I, E, and A respectively.
Example 2
Input
12
*.*#.***#.*.
*.*#..*.#***
***#.***#*.*
Output
U#I#A
Explanation
As it can be seen that the stars make the image of the alphabet U, I, and A.
Possible solution:
Input:
12
*.*#.***#.*.
*.*#..*.#***
***#.***#*.*
Solution: C++
#include <iostream>
using namespace std;
int main()
{
int n,x1,y1;
cin>>n;
char x[3][n];
for(int i=0;i<3;i++)
{
for(int j=0;j<n;j++)
{
cin>>x[i][j];
}
}
for(int i=0;i<n;i++)
{
if(x[0][i]=='#' && x[1][i]=='#' && x[2][i]=='#')

Page 26 of 66
Accenture ADVANCED CODING

{
cout<<'#';
}
else if(x[0][i]=='.' && x[1][i]=='.' && x[2][i]=='.')
{}
else
{
char a,b,c,a1,b1,c1,a2,b2,c2;
x1 = i;
a = x[0][x1];
b = x[0][x1+1];
c = x[0][x1+2];
a1 = x[1][x1];
b1 = x[1][x1+1];
c1 = x[1][x1+2];
a2 = x[2][x1];
b2 = x[2][x1+1];
c2 = x[2][x1+2];
if(a=='.' && b=='*' && c=='.' && a1=='*' && b1=='*' && c1=='*' && a2=='*' && b2=='.' && c2=='*')
{
cout<<"A";
i = i + 2;
}
if(a=='*' && b=='*' && c=='*' && a1=='*' && b1=='*' && c1=='*' && a2=='*' && b2=='*' &&
c2=='*')
{
cout<<"E";
i = i + 2;
}
if(a=='*' && b=='*' && c=='*' && a1=='.' && b1=='*' && c1=='.' && a2=='*' && b2=='*' && c2=='*')
{
cout<<"I";
i = i + 2;
}
if(a=='*' && b=='*' && c=='*' && a1=='*' && b1=='.' && c1=='*' && a2=='*' && b2=='*' && c2=='*')
{
cout<<"O";
i = i + 2;
}

Page 27 of 66
Accenture ADVANCED CODING

if(a=='*' && b=='.' && c=='*' && a1=='*' && b1=='.' && c1=='*' && a2=='*' && b2=='*' && c2=='*')
{
cout<<"U";
i = i + 2;
}
}
}
}
Output
Solution: Java
import [Link].*;
public class Main {
public static void main(String[] args) throws Exception {
// Your code here!
Scanner sc=new Scanner( [Link] );
int n=[Link]();
char gal[][] = new char [3][n];
for(int i=0;i<3;i++){
String a=[Link]();
for(int j=0;j<n;j++)
gal[i][j]=[Link](j);
}
for(int i=0;i<n;)
{
if(gal[0][i]=='#')//||gal[0][i+1]=='#')
{
[Link]("#"); i++; continue;
}
if(gal[0][i]=='.' && gal[1][i]=='.' && gal[2][i]=='.')
{
i++; continue;
}
if(gal[0][i]=='.' && gal[0][i+2]=='.' && gal[2][i+1]=='.')
[Link]("A");
else if(gal[1][i+1]=='.')
{
if(gal[0][i+1]=='.')
[Link]("U");
else

Page 28 of 66
Accenture ADVANCED CODING

[Link]("O");
}
else if(gal[1][i]=='.' && gal[1][i+2]=='.')
[Link]("I");
//else if(gal[0][i]=='#')
//[Link]("#");
else
[Link]("E");

i+=3;
}
// [Link]("XXXXXXXX");
}
Solution Python
from collections import deque
def initialize():
q = deque()
#A
s = ""
[Link](['.', '*', '*'])
[Link](['*', '*', '.'])
[Link](['.', '*', '*'])
s = ''.join(map(str, q))
vowels[s] = 'A'
[Link]()
#E
[Link](['*', '*', '*'])
[Link](['*', '*', '*'])
[Link](['*', '*', '*'])
s = ''.join(map(str, q))
vowels[s] = 'E'
[Link]()
#I
[Link](['*', '.', '*'])
[Link](['*', '*', '*'])
[Link](['*', '.', '*'])
s = ''.join(map(str, q))
vowels[s] = 'I'
[Link]()

Page 29 of 66
Accenture ADVANCED CODING

#O
[Link](['*', '*', '*'])
[Link](['*', '.', '*'])
[Link](['*', '*', '*'])
s = ''.join(map(str, q))
vowels[s] = 'O'
[Link]()
#U
[Link](['*', '*', '*'])
[Link](['.', '.', '*'])
[Link](['*', '*', '*'])
s = ''.join(map(str, q))
vowels[s] = 'U'
[Link]()
return vowels
vowels = {}
vowels = initialize()
n = int(input())
x = []
for i in range(n):
[Link](['.', '.', '.'])
for i in range(3):
l = []
l = list(input())
for j in range(n):
x[j][i] = l[j]
constellation = ""
star = deque()
for i in range(n):
if len(star) ==3:
s = ''.join(map(str, star))
if s in vowels:
constellation += vowels[s]
[Link]()
else:
[Link]()
if x[i]==['#', '#', '#']:
[Link]()
constellation += '#'

Page 30 of 66
Accenture ADVANCED CODING

continue
[Link](x[i])
if len(star)==3:
s = ''.join(map(str, star))
if s in vowels:
constellation += vowels[s]
print(constellation, end="")

18. Prime Time Again

Here on earth, our 24-hour day is composed of two parts, each of 12 hours. Each hour in each part
has a corresponding hour in the other part separated by 12 hours: the hour essentially measures the
duration since the start of the daypart. For example, 1 hour in the first part of the day is equivalent to
13, which is 1 hour into the second part of the day.
Now, consider the equivalent hours that are both prime numbers. We have 3 such instances for a 24-
hour 2-part day:
5~17
7~19
11~23
Accept two natural numbers D, P >1 corresponding respectively to a number of hours per day and the
number of parts in a day separated by a space. D should be divisible by P, meaning that the number of
hours per part (D/P) should be a natural number. Calculate the number of instances of equivalent
prime hours. Output zero if there is no such instance. Note that we require each equivalent hour in
each part in a day to be a prime number.
Example:
Input: 24 2
Output: 3 (We have 3 instances of equivalent prime hours: 5~17, 7~19, and 11~23.)
Constraints
10 <= D < 500
2 <= P < 50
Input
The single line consists of two space-separated integers, D and P corresponding to the number of.
hours per day and number of parts in a day respectively
Output
Output must be a single number, corresponding to the number of instances of equivalent prime
number, as described above
Example 1
Input
36 3
Output
2

Page 31 of 66
Accenture ADVANCED CODING

Explanation
In the given test case D = 36 and P = 3
Duration of each daypart = 12
2~14~X
3~15~X
5~17~29 - an instance of equivalent prime hours
7~19~31 - an instance of equivalent prime hours
11~23~X
Hence the answer is 2.
Possible solution:
Input:
49 7
Solution: C++
#include<bits/stdc++.h>
using namespace std;
bool isprime(int n)
{
if(n==1)
return false;
for(int i=2;i<=(int)sqrt(n);i++)
{
if(n%i==0)
return false;
}
return true;
}
int main()
{
int D,P,i,j,p,t=1;
cin>>D>>P;
p=D/P;
int time[p][P];
for(i=0;i<P;i++)
{
for(j=0;j<p;j++)
{
time[j][i]=t++;
}
}

Page 32 of 66
Accenture ADVANCED CODING

t=0;
for(i=0;i<p;i++)
{
bool flag=true;
for(j=0;j<P;j++)
{
if(!isprime(time[i][j]))
{
flag=false;
break;
}
}
if(flag)
t++;
}
cout<<t;
}
Solution: Java
import [Link].*;
public class Main {
public static booleanisprime(int n)
{
if(n==1) return false;
for(int i=2;i<=(int) [Link](n) ; i++){
if(n%i==0)
return false;
}
return true;
}
public static void main(String[] args) throws Exception {
// Your code here!
Scanner sc= new Scanner([Link]);
// [Link]("XXXXXXXX");
int i,j,D,P,p,t=1;
D=[Link]();
P=[Link]();
p=D/P;
int time[][] = new int [p][P];
for(i=0;i<P;i++){

Page 33 of 66
Accenture ADVANCED CODING

for(j=0;j<p;j++){
time[j][i]=t++;
}
}
t=0;
for(i=0;i<p;i++)
{
boolean flag=true;
for(j=0;j<P;j++)
{
if(!isprime(time[i][j]))
{
flag=false; break;
}
}
if(flag) t++;
}
[Link](t);
}
}
Solution: Python
primes = set()
def generate(lim):
for i in range(2, lim):
x=1
for j in primes:
if (i%j==0):
x=0
break
if x==1:
[Link](i)
d, p = map(int, input().split())
generate(d)
c=0
inv = d//p
for i in range(inv):
if i in primes:
x=1
for j in range(1, p):

Page 34 of 66
Accenture ADVANCED CODING

if (j*inv+i) not in primes:

x=0
break
if x==1:
c+=1
print(c)

19. Minimum Gifts

A Company has decided to give some gifts to all of its employees. For that, the company has given
some rank to each employee. Based on that rank, the company has made certain rules to distribute
the gifts.
The rules for distributing the gifts are:
Each employee must receive at least one gift.
Employees having higher ranking get a greater number of gifts than their neighbours.
What is the minimum number of gifts required by the company?
Constraints
1 < T < 10
1 < N < 100000
1 < Rank < 10^9
Input
First line contains integer T, denoting the number of test cases.
For each test case:
First line contains integer N, denoting the number of employees.
Second line contains N space separated integers, denoting the rank of each employee.
Output
For each test case print the number of minimum gifts required on a new line.
Example 1
Input
2
5
12152
2
12
Output
7
3
Explanation
For test case 1, adhering to the rules mentioned above,
Employee # 1 whose rank is 1 gets one gift
Employee # 2 whose rank is 2 gets two gifts

Page 35 of 66
Accenture ADVANCED CODING

Employee # 3 whose rank is 1 gets one gift

Employee # 4 whose rank is 5 gets two gifts
Employee # 5 whose rank is 2 gets one gift
Therefore, total gifts required is 1 + 2 + 1 + 2 + 1 = 7
Similarly, for testcase 2, adhering to rules mentioned above,
Employee # 1 whose rank is 1 gets one gift
Employee # 2 whose rank is 2 gets two gifts
Therefore, total gifts required is 1 + 2 = 3
Possible solution:
Input:
2
5
12152
2
12
Solution: C++
#include<bits/stdc++.h>
using namespace std;
long longarr[100010];
long longbrr[100010];
int main()
{
int test_case;
cin>>test_case;
for(int i = 1; i<= test_case; i++)
{
int n;
long long gift = 0, temp = 0;
cin>> n;
for(int i = 0; i< n; i++)
{
cin>>arr[i];
}
brr[0] = 1;
for(int i = 1; i< n; i++)
{
if(arr[i] >arr[i-1])
{
brr[i] = brr[i-1] + 1;

Page 36 of 66
Accenture ADVANCED CODING

}
else
{
brr[i] = 1;
}
}
gift = brr[n-1];
for(int i = n-2; i>= 0; i--)
{
if(arr[i] >arr[i+1])
{
temp = brr[i+1] + 1;
}
else
temp = 1;
gift = gift + max(temp, brr[i]);
brr[i] = temp;
}
cout<< gift <<endl;
}
return 0 ;
}
Solution: Java
import [Link];
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int T = [Link]();
while (T-- > 0) {
int n = [Link]();
int[] ar = new int[n];
for (int i = 0; i< n; i++)
ar[i] = [Link]();
int[] gifts = new int[n];
gifts[0] = 1;
// Left to Right Neighbors
for (int i = 1; i< n; i++) {
if (ar[i] >ar[i - 1])
gifts[i] = gifts[i - 1] + 1;

Page 37 of 66
Accenture ADVANCED CODING

else
gifts[i] = 1;
}
// Right to Left Neighbors
for (int i = n - 2; i>= 0; i--) {
if (ar[i] >ar[i + 1] && gifts[i] <= gifts[i + 1])
gifts[i] = gifts[i + 1] + 1;
}
long total = 0;
for (int gift : gifts)
total += gift;
[Link](total);
}
}
}
Solution: Python
t = int(input())
while t>0:
n = int(input())
a = list(map(int, input().split()))
gifts = [1]
#[Link](1)
for i in range(1, n):
if a[i] > a[i-1]:
[Link](gifts[i-1]+1)
else:
[Link](1)
for i in range(n-2,-1,-1):
if a[i]>a[i+1]:
gifts[i] = max (1 + gifts[i+1], gifts[i])
g=0
for i in range(n):
g += gifts[i]
print(g)
t-=1
20. Minimize the sum
Given an array of integers, perform atmost K operations so that the sum of elements of final array is
minimum. An operation is defined as follows -
Consider any 1 element from the array, arr[i].

Page 38 of 66
Accenture ADVANCED CODING

Replace arr[i] by floor(arr[i]/2).

Perform next operations on the updated array.
The task is to minimize the sum after utmost K operations.
Constraints
1 <= N, K <= 10^5.
Input
First line contains two integers N and K representing size of array and maximum numbers of
operations that can be performed on the array respectively.
Second line contains N space separated integers denoting the elements of the array, arr.
Output
Print a single integer denoting the minimum sum of the final array.
Input
43
20 7 5 4
Output
17
Explanation
Operation 1 -> Select 20. Replace it by 10. New array = [10, 7, 5, 4]
Operation 2 -> Select 10. Replace it by 5. New array = [5, 7, 5, 4].
Operation 3 -> Select 7. Replace it by 3. New array = [5,3,5,4].
Sum = 17.
Possible Solution
Input:
43
20 7 5 4
Solution: C++
#include<bits/stdc++.h>
using namespace std;
int main()
{
long int n,k,temp,sum=0;
cin>>n;
cin>>k;
vector<int> v;
for(int i=0;i<n;i++)
{
cin>>temp;
sum=sum + temp;
v.push_back(temp);

Page 39 of 66
Accenture ADVANCED CODING

}
make_heap([Link](),[Link]());
long int maxi = 0,res = 0;
for(int i=0;i<k;i++)
{
maxi=[Link]();
sum-=maxi;
pop_heap([Link](), [Link]());
v.pop_back();
res = maxi / 2;
sum+=res;
v.push_back(res);
push_heap([Link](),[Link]());
}
cout<<sum;
}
Solution: Java
import [Link].*;
public class Main {
public static void main(String[] args) throws Exception {
// Your code here!
Scanner sc= new Scanner([Link]);
// [Link]("XXXXXXXX")
int n,k,i,s=0;
n=[Link]();
k=[Link]();
int a[]= new int [n];
for(i=0;i<n;i++) a[i]=[Link]();
while(k-- > 0)
{
int mx=0,p=0;
for(i=0;i<n;i++){
if(a[i]>mx) {
mx=a[i];
p=i;
}
}
a[p]=a[p]/2;
}

Page 40 of 66
Accenture ADVANCED CODING

for(i=0;i<n;i++) s+=a[i];
[Link](s);
}
}
Solution: Python
n, k = map(int, input().split())
frequency = []
for i in range(100000):
[Link](0)
sum = 0
a = list(map(int, input().split()))
for i in range(n):
frequency[a[i]] += 1
j = 100000-1
while j>0 and k>0:
while frequency[j]!=0 and k>0:
k -= 1
frequency[j] -=1
frequency[j//2] += 1
j-=1
for i in range(100000):
sum += i*frequency[i]
print(sum)

21. Railway Station

Given schedule of trains and their stoppage time at a Railway Station, find minimum number of
platforms needed.
Note -
If Train A's departure time is x and Train B's arrival time is x, then we can't accommodate Train B on
the same platform as Train A.
Constraints
1 <= N <= 10^5
0 <= a <= 86400
0 < b <= 86400
Number of platforms > 0
Input
First line contains N denoting number of trains.
Next N line contain 2 integers, a and b, denoting the arrival time and stoppage time of train.
Output
Single integer denoting the minimum numbers of platforms needed to accommodate every train.

Page 41 of 66
Accenture ADVANCED CODING

Example 1
Input
3
10 2
5 10
13 5
Output
2
Explanation
The earliest arriving train at time t = 5 will arrive at platform# 1. Since it will stay there till t = 15,
train arriving at time t = 10 will arrive at platform# 2. Since it will depart at time t = 12, train
arriving at time t = 13 will arrive at platform# 2.
Example 2
Input
2
24
62
Output
2
Explanation
Platform #1 can accommodate train 1.
Platform #2 can accommodate train 2.
Note that the departure of train 1 is same as arrival of train 2, i.e. 6, and thus we need a separate
platform to accommodate train 2.
Possible Solution
Input:
2
24
62
Solution: C++
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n],b[n];
for(int i=0;i<n;i++)
{

Page 42 of 66
Accenture ADVANCED CODING

cin>>a[i]>>b[i];
b[i]=a[i]+b[i];
}
sort(a,a+n);
sort(b,b+n);
int p=1,r=1,i=1,j=0;
while(i<n && j<n)
{
if(a[i]<=b[j])
{
p++;
i++;
}
else if(a[i]>b[j])
{
p--;
j++;
}
if(p>r)
r=p;
}
cout<<r;
}
Solution: Java
import [Link];
import [Link];
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
int[] arr = new int[n];
int[] dep = new int[n];
for (int i = 0; i< n; i++) {
arr[i] = [Link]();
int stoppage = [Link]();
dep[i] = arr[i] + stoppage;
}
[Link](arr);
[Link](dep);

Page 43 of 66
Accenture ADVANCED CODING

int i = 1, j = 0, currPlatforms = 1, ans = 1;

while (i< n && j < n) {
if (arr[i] <= dep[j]) {
i++;
currPlatforms++;
}
else {
currPlatforms--;
j++;
}
ans = [Link](ans, currPlatforms);
}
[Link](ans);
}
}
Solution: Python
n = int(input())
arr = []
dep = []
for i in range(n):
a, d = map(int, input().split())
d += a
[Link](a)
[Link](d)
[Link]()
[Link]()
i=1
j=0
plf = 1
maxplf = 1
while i<n and j<n:
if arr[i] <= dep[j]:
i+=1
plf+=1
maxplf = max ( maxplf, plf )
continue
j+=1
plf-=1
print(maxplf)

Page 44 of 66
Accenture ADVANCED CODING

21. Count Pairs

Given an array of integers A, and an integer K find number of happy elements.
Element X is happy if there exists at least 1 element whose difference is less than K i.e. an element X is
happy if there is another element in the range [X-K, X+K] other than X itself.
Constraints
1 <= N <= 10^5
0 <= K <= 10^5
0 <= A[i] <= 10^9
Input
First line contains two integers N and K where N is size of the array and K is a number as described
above. Second line contains N integers separated by space.
Output
Print a single integer denoting the total number of happy elements.
Example 1
Input
63
5 5 7 9 15 2
Output
5
Explanation
Other than number 15, everyone has at least 1 element in the range [X-3, X+3]. Hence they are all
happy elements. Since these five are in number, the output is 5.
Example 2
Input
32
135
Output
3
Explanation
All numbers have at least 1 element in the range [X-2, X+2]. Hence they are all happy elements. Since
these three are in number, the output is 3.
Possible Solution
Input:
32
135
Solution: C++
#include <bits/stdc++.h>
using namespace std;
int pairs(int elementlst[],int n,int z){

Page 45 of 66
Accenture ADVANCED CODING

int count=0;
for(int i=0;i<n;i++){
int a=elementlst[i];
int id1=i;
int id2=i;
if(i==0){
while(elementlst[id2+1]==a)
id2+=1;
if(elementlst[id2+1]<=a+z&&elementlst[id2+1]>=a-z)
count+=1;
}
else if(i<n-1){
while(elementlst[id2+1]==a)
id2+=1;
while(elementlst[id1-1]==a)
id1-=1;
if(((elementlst[id1-1]<=a+z) && (elementlst[id1-1]>=a-z)) || ((elementlst[id2+1]<=a+z) &&
(elementlst[id2+1]>=a-z)))
count+=1;
}
else{
while(elementlst[id1-1]==a)
id1-=1;
if(elementlst[id1-1]<=a+z&&elementlst[id1-1]>=a-z)
count+=1;
}
}
return count;
}
int main() {
int n,z;
cin>>n>>z;
int elementlst[n];
for(int i=0;i<n;i++){
cin>>elementlst[i];
}
sort(elementlst,elementlst+n);
cout<<pairs(elementlst,n,z);
return 0;

Page 46 of 66
Accenture ADVANCED CODING

}
Solution: Java
import [Link].*;
public class Main {
public static int pairs(int a[], int n , int z)
{
int c=0,i;
for(i=0;i<n;i++)
{
int aa=a[i];
int id1=i; int id2=i;
if(i==0)
{
while(a[id2+1]==aa)
id2++;
if(a[id2+1]<=aa+z&& a[id2+1]>=aa-z)
c++;
}
else if(i<n-1)
{
while(a[id2+1]==aa)
id2+=1;
while(a[id1-1]==aa)
id1-=1;
if(((a[id1-1]<=aa+z) && (a[id1-1]>=aa-z)) || (
(a[id2+1]<=aa+z) && (a[id2+1]>=aa-z)))
c+=1;
}
else
{
while(a[id1-1]==aa)
id1-=1;
if(a[id1-1]<=aa+z&& a[id1-1]>=aa-z)
c+=1;
}
}
return c;
}
public static void main(String[] args) throws Exception {

Page 47 of 66
Accenture ADVANCED CODING

// Your code here!

Scanner sc= new Scanner([Link]);
// [Link]("XXXXXXXX")
int n,k,i,s=0;
n=[Link]();
k=[Link]();
int a[]= new int [n];

for(i=0;i<n;i++) a[i]=[Link]();
[Link](a);
[Link](pairs(a,n,k));
}
}
Solution: Python
n, k = map(int, input().split())
a = set()
a = set(map(int, input().split()))
a = list(a)
if n==1:
print("0")
else:
a = sorted(a)
c=0
for i in range(1, len(a)-1):
if a[i]-a[i-1]>k and a[i+1]-a[i]>k :
c += 1
if a[1]-a[0]>k:
c+=1
if a[len(a)-1]-a[len(a)-2]>k:
c +=1
print(n-c)

23. Critical Planets

The war between Republic and Separatists is escalating. The Separatists are on a new offensive. They
have started blocking the path between the republic planets (represented by integers) so that these
planets surrender due to the shortage of food and supplies. The Jedi council has taken note of the
situation and they have assigned Jedi Knight Skywalker and his Padawan Ahsoka to save the critical
planets from blockade (Those planets or system of planets which can be accessed by only one path
and may be lost if that path is blocked by separatist).

Page 48 of 66
Accenture ADVANCED CODING

Skywalker is preparing with the clone army to defend the critical paths. He has assigned Ahsoka to
find the critical planets. Help Ahsoka to find the critical planets(C) in ascending order. You only need
to specify those planets which have only one path between them and they cannot be accessed by any
other alternative path if the only path is compromised.
Constraints
M <= 10000
N <= 7000
Input
First line contains two space separated integers M and N, where M denotes the number of paths
between planets and N denotes the number of planets.
Next M lines, each contains two space separated integers, representing the planet numbers that have
a path between them.
Output
C lines containing one integer representing the critical planet that they need to save in ascending
order of the planet number if no planet is critical then print -1
Time Limit
1
Example 1
Input
34
01
12
23
Output
0
1
2
3
Explanation

Since all the planets are connected with one path and cannot be accessed by any alternative paths
hence all the planets are critical.
Example 2
Input
76
02
01
12

Page 49 of 66
Accenture ADVANCED CODING

23
45
34
35
Output
2
3
Explanation

If the republic loose the path between 2 and 3 then the two system of planets will not be able to
communicate with each other. Hence 2 and 3 are critical planets.
Possible Solution:
Input
34
01
12
23
Solution: C++
#include <bits/stdc++.h>
typedef long long int lli;
#define pb push_back
using namespace std;
vector<int>adj[100001];
int visited[100001] , in[100001] ,low[100001];
int timer;
set<int> s;
void dfs(int node , int pre)
{
visited[node] = 1;
in[node] = low[node] = timer;
timer++;
for(int i : adj[node])
{
if(i == pre)

Page 50 of 66
Accenture ADVANCED CODING

continue;
if(visited[i] == 1)
{
low[node] = min(low[node] , in[i]);
}
else
{
dfs(i , node);
if(low[i] > in[node])
[Link](node) , [Link](i);
low[node] = min(low[node] , low[i]);
}
}
}
int main()
{
int edge, vertex , a , b;
cin>> edge >> vertex;
for(int i = 0;i <edge;i++)
{
cin>> a >> b;
adj[a].pb(b);
adj[b].pb(a);
}
dfs(0 , -1);
for(int i : s)
cout<<i<<endl;
return 0;
}
Solution: Java
import [Link];
import [Link];
import [Link];
import [Link];
public class Main {
static List<List<Integer>> graph;
static TreeSet<Integer>criticalPlanets;
static boolean[] visited;
static int[] inTime;

Page 51 of 66
Accenture ADVANCED CODING

static int[] low;

static int timer = 0;
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int m = [Link]();
int n = [Link]();
graph = new ArrayList<>(n);
for (int i = 0; i< n; i++)
[Link](new ArrayList<>());
visited = new boolean[n];
inTime = new int[n];
low = new int[n];
criticalPlanets = new TreeSet<>();
for (int i = 0; i< m; i++) {
int u = [Link]();
int v = [Link]();
[Link](u).add(v);
[Link](v).add(u);
}
dfs(0, -1);
for (int i :criticalPlanets)
[Link](i);
}
public static void dfs(int node, int parent) {
visited[node] = true;
inTime[node] = low[node] = timer++;
for (int neighbour :[Link](node)) {
if (neighbour == parent)
continue;
if (visited[neighbour])
low[node] = [Link](low[node], inTime[neighbour]);
else {
dfs(neighbour, node);
if (low[neighbour] >inTime[node]) {
[Link](neighbour);
[Link](node);
}
low[node] = [Link](low[node], low[neighbour]);
}

Page 52 of 66
Accenture ADVANCED CODING

}
}
}
Solution: Python
timer=0
def dfs (cur, par, timer):
vis[cur]=1
if cur!=0:
low[cur] = trav[cur] = trav[par] + 1
timer += 1
for i in g[cur]:
if i == par:
continue
if vis[i]==1:
low[cur] = min ( low[cur], trav[i] )
else:
dfs(i, cur, timer)
if low[i]>low[cur]:
[Link](i)
[Link](cur)
low[cur] = min (low[cur], low[i])
e, n = map(int, input().split())
g = []
vis = []
low = []
trav = []
for i in range(n):
l = []
[Link](0)
[Link](0)
[Link](0)
[Link](l)
for i in range(e):
a, b = map(int, input().split())
g[a].append(b)
g[b].append(a)
defend = set()
dfs(0, -1, timer)
defend = list(defend)

Page 53 of 66
Accenture ADVANCED CODING

[Link]()
for i in defend:
print(i)
24. Hack the money
You are a bank account hacker. Initially you have 1 rupee in your account, and you want exactly N
rupees in your account. You wrote two hacks, First hack can multiply the amount of money you own
by 10, while the second can multiply it by 20. These hacks can be used any number of time. Can you
achieve the desired amount N using these hacks?
Constraints
1<=T<=100
1<=N<=1012
Input:
The first line of the input contains a single integer T denoting the number of test cases.
The description of T test cases follows. The first and only line of each test case contains a single
integer N.
Output:
For each test case, print a single line containing the string "Yes" if you can make exactly N rupees or
"No" otherwise.
Sample Input:
5
1
2
10
25
200
Output:
Yes
No
Yes
No
Yes
Explanation:
In the last case hacker can get Rs. 200 by first using 10x hack and then using 20x hack once.
1 -> 10 -> 200
Test Cases:

[Link]. Input Output

5
Yes
1
No
2
Test Case 1 Yes
10
No
25
Yes
200

Page 54 of 66
Accenture ADVANCED CODING

3
No
101
Test Case 2 No
52
No
124
5
No
1820
No
513
Test Case 3 No
450
No
884
Yes
2000
2
Yes
Test Case 4 2000
No
3000
3
Yes
1
Test Case 5 Yes
10
Yes
200
2
Yes
Test Case 6 20
Yes
200
5
Yes
2000
Yes
200
Test Case 7 No
2
Yes
10
Yes
1
2
Yes
Test Case 8 20
Yes
10000
1
Test Case 9 No
1001
Code Solution in C++
#include<iostream>
using namespace std;
bool hack (long long, long long);
int main()
{
int tests;
cin>>tests;
for(int i=0;i<tests;i++)
{
long long target;
cin>>target;

Page 55 of 66
Accenture ADVANCED CODING

if(hack(target, 1))
cout<<”Yes”<<endl;
}
return 0;
}
bool back (long long target, long long current)
{
if(current==target) return true;
else if(current>target) return false;
else
{
if(hack(target, 10*current))
return true;
if(hack(target,20*current))
return true;
}
return false;
}
25. Lowest Common Ancestor
Write a program to find a common ancestor of a given two numbers in the tree. Let T be the root of a
tree. The lowest common ancestor between two nodes n1 and n2 is defined as the lowest node in T.
Which has both n1 and n2 as descendants (where we allow a node to be a descendant of itself). The
LCA of n1 and n2 in T is the shared ancestor of n1 and n2, which is located farthest from the root.
Computation of the Lowest common ancestor is useful. For instance, as part of a procedure for
determining the distance between the pairs of a node in a tree. The distance from n1 to n2 can be
computed as a distance from a root to n1. Plus, the distance from a root to n2. Later, subtract two
times the distance from a root to their lowest common ancestor.
Format:
Input:
6
3
1
4
2
-1
36
Output:
6
Test Cases:

[Link]. Input Output

Page 56 of 66
Accenture ADVANCED CODING

5 3 7 2 4 6 8 -1
Test Case 1 3
24
6 3 1 4 2 -1
Test Case 2 6
36
20 8 4 12 10 14 22 -1
Test Case 3 8
4 12
20 8 4 12 10 14 22 -1
Test Case 4 12
10 14
20 8 4 12 10 14 22 -1
Test Case 5 20
10 22

Code Solution in C++

#include<bits/stdc++.h>
using namespace std;
struct node
{
int data;
struct node *left, *right;
};
struct node *root;
struct node* create(int n)
{
struct node *temp = (struct node*) malloc (sizeof(struct node*));
temp->data=n’
temp->right=temp->=NULL;
}
struct node*lca(struct node*root, int n1, int n2)
{
of(root ->data>n1 && root->data>n2)
return lca(root->left, n1, n2);
else if (root->data<n1 && root->data<n2)
return lca (root->right, n1, n2);
return root;
}
void insert (struct node *temp, struct node *t)
{
if (t->data<temp->data && t->right! = NULL)
insert(temp, t->right);

Page 57 of 66
Accenture ADVANCED CODING

if (t->data<temp->data && t->right! == NULL)

t->right=temp;
if(t->data>temp->data && t->left! = NULL)
insert(temp, t->left);
if(t->data>temp->data && t->left! == NULL)
t->left=temp;
}
int main()
{
int n;
cin>>n;
while(n!=*1)
{
struct node *newnod = create(n);
if(root==NULL)
root=newode;
else
insert(newnode, root);
cin>>n;
}
int n1, n2;
cin>>n1>>n2;
struct node *temp = lca(root, n1, n2);
cout<<temp->data;
}

26. Robot Move

A Robot wants to move through a cave grid of size M x N. (M- Rows N- Columns). It starts from (0,0)
and destination is (M-1,N-1). It can only move right or down. Calculate the total number of ways
robot can reach the destination.
Sample Input:
55
Output:
70
Test Cases:

[Link]. Input Output

5
Test Case 1 70
5

Page 58 of 66
Accenture ADVANCED CODING

10
Test Case 2 48620
10
2
Test Case 3 5
5
3
Test Case 4 6
3
4
Test Case 5 20
4
6
Test Case 6 462
7
6
Test Case 7 252
6
15
Test Case 8 40116600
15
9
Test Case 9 12870
9
11
Test Case 10 184756
11

Code Solution in C++

#include <iostream>
using namespace std;
int total_ways(int cr, int cc, int r, int c)
{
if(cr> r || cc > c)
{
return 0;
}
if(cr == r && cc == c)
{
return 1;
}
return total_ways(cr, cc+1, r, c) + total_ways(cr+1, cc, r, c);
}
int main()
{
int m,n;
cin>>m>>n;

Page 59 of 66
Accenture ADVANCED CODING

cout<<total_ways(0,0,m-1,n-1);
return 0;
}
27. Nearest Prime
Joy is a hacker at hackerclub and he got a new problem on prime numbers. The problem states that
given an integer N find the nearest prime number to N. If multiple answer is possible then output the
smallest one of them. There are T number of test cases.
1<=N<106
1<=T<=2*106
Input:
First line of input contains an Integer T denoting the number of test cases.
Next each of the T lines contain one integer N.
Output:
Output the nearest prime number possible to N in a new line
Sample Input:
3
51
12
65
Output:
53
11
67
Test Cases:

[Link]. Input Output

3
53
51
Test Case 1 11
12
67
65
2
449
Test Case 2 452
523
526
5 1423
1425 8521
Test Case 3 8521 457
456 251
254 997

Page 60 of 66
Accenture ADVANCED CODING

1000
1
Test Case 4 53239
53246
3
13
14
Test Case 5 23
25
31
32
6
53
52
43
45
61
Test Case 6 63
97
98
79
78
31
32
4
751
752
2371
Test Case 7 2365
8963
8963
5
6
1
Test Case 8 100003
99999
5
5
5
5
6
Test Case 9 7
9
7
8
7
7
1
Test Case 10 557
555

Code Solution in C++

#include<bits/stdc++.h>
using namespace std;
typedef long long 11;
bool prime(11 n){
if(n<=1)
return 0;

Page 61 of 66
Accenture ADVANCED CODING

if(n==2)
return 1;
for(11 i=2;i*<=n;i++){
if(n%i==0)
return 0;
}
return 1;
}
int main(){
11 i, j, k, t, n;
scanf(“%22d”, &n);
for (i=n, j=n;;i--, j++){
if(i>=0 and prime(i) ==1){
printf(“%11d\n”,i);
break;
}else if (prime (j)==1){
Printf(“%11d\n”, j);
Break;
}
}
}
}
28. Permutations - All of them
"I'm not a fan of having kids memorize formulas, and I'm even less of a fan of pushing them to learn
those formulas," says Mr. John, 7th grade Math teacher. Maybe he has got a point. He believes in
teaching the logic rather than the formula. Anyway, we aren't here to weigh/debate about his
opinions. All we gotta do is help Mr. John and his students by writing an algorithm that can calculate
& print all the permutations of a given number in strictly sorted order. Remember, Mr. John is gonna
use your algorithm to demonstrate permutations in his next class.
Input Format:
The input consists of a string
Output Format:
Print all the permutations of the given string
Refer the sample output for formatting
Sample Input:
abc
Sample Output:
abc
acb

Page 62 of 66
Accenture ADVANCED CODING

bac
bca
cab
cba
Test Cases:
[Link]. Input Output
abc
acb
bac
Test Case 1 abc
bca
cab
cba
abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
Test Case 2 abcd
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba
123
Test Case 3 123
132

Page 63 of 66
Accenture ADVANCED CODING

213
231
312
321
12
Test Case 4 12
21
Test Case 5 a a
aet
ate
eat
Test Case 6 eat
eta
tae
tea
ot
Test Case 7 to
to
ehl
elh
hel
Test Case 8 hel
hle
leh
lhe
cde
ced
cde dce
Test Case 9
dec
ecd
edc
Test Case 10 s s

Code Solution in C++

#include<stdio.h>
#include<string.h>
void sort(char arr[], int n);
void permutationWrapper(char a[]. Int n);
void permute(char a[], int n, int selected[], int used[], int index);
#define MAX_SIZE 20
int main()

Page 64 of 66
Accenture ADVANCED CODING

{
// Get the n elements as an input and store in arr
char arr[MAX_SIZE];
scanf(“%s”, arr);
int n = strlen(arr);
permutationWrapper(arr, n);
return 0;
}
void sort(char arr[], int n)
{
int i, j;
for(i =1; i<n; i++)
{
int tmp = arr[i];
for(j = i-1; j >=0; j--)
{
if(arr[j + 1] <arr[j])
{
arr[j +1] = arr[j];
}
Else
{
break;
}
}
arr[j + 1] = tmp;
}
}
void permutationWrapper(char a[], int n)
{
sort(a, n);
int selected[MAX_SIZE] = {}, used[MAX_SIZE] = {};
permute(a, n, selected, used, 0);
}
void permute(char a[], int n, int selected[], int used[], int index)
{
int i;
if (index == n)
{

Page 65 of 66
Accenture ADVANCED CODING

for (i=0; i<n; i++)

{
Printf)”%c”, selected [i]);
}
Printf(“\n”);
return;
}
for(i=0; i<n; i++)
{
if(used[i] == 1)
{
continue;
}
used[i] = 1;
selected[index] = a[i];
permute(a, n, selected, used, index + 1);
used[i] = 0;
}
}

Page 66 of 66