Solutions:
C Language
#include <stdio.h>
int main()
{
int n; scanf("%d",&n);
int arr[n];
for(int i=0 ; i<n ; i++){
scanf("%d",&arr[i]);
}
int left=0,right=n-1,mid,pre,nxt;
if(arr[0] != arr[1]){
printf("%d ",arr[0]);
}
else if(arr[n-1] != arr[n-2]){
printf("%d ",arr[n-1]);
}
else{
while(left <= right){
mid = ((right-left)/2)+left;
pre = mid-1;
nxt = mid+1;
if((arr[pre] != arr[mid]) && (arr[nxt] != arr[mid])){
printf("%d ",arr[mid]);
break;
}
else if(mid%2==0){
if(arr[pre] == arr[mid])
right = mid - 1;
else
left = mid + 1;
}
else{
if(arr[pre] == arr[mid])
left = mid + 1;
else
right = mid - 1;
}
}
}
return 0;
}
C++
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n; cin >> n;
vector<int> v(n);
for(int i=0 ; i<n ; i++){
cin >> v[i];
}
int left=0,right=n-1,mid,pre,nxt;
if(v[0] != v[1]){
cout << v[0];
}
else if(v[n-1] != v[n-2]){
cout << v[n-1];
}
else{
while(left <= right){
mid = ((right-left)/2)+left;
pre = mid-1;
nxt = mid+1;
if((v[pre] != v[mid]) && (v[nxt] != v[mid])){
cout << v[mid];
break;
}
else if(mid%2==0){
if(v[pre] == v[mid])
right = mid - 1;
else
left = mid + 1;
}
else{
if(v[pre] == v[mid])
left = mid + 1;
else
right = mid - 1;
}
}
}
return 0;
}
JAVA
import java.util.*;
public class Main
{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[n];
for(int i=0 ; i<n ; i++){
arr[i] = sc.nextInt();
}
int left=0,right=n-1,mid,pre,nxt;
if(arr[0] != arr[1]){
System.out.print(arr[0]);
}
else if(arr[n-1] != arr[n-2]){
System.out.print(arr[n-1]);
}
else{
while(left <= right){
mid = ((right-left)/2)+left;
pre = mid-1;
nxt = mid+1;
if((arr[pre] != arr[mid]) && (arr[nxt] != arr[mid])){
System.out.print(arr[mid]);
break;
}
else if(mid%2==0){
if(arr[pre] == arr[mid])
right = mid - 1;
else
left = mid + 1;
}
else{
if(arr[pre] == arr[mid])
left = mid + 1;
else
right = mid - 1;
}
}
}
}
}
PYTHON
n = int(input())
a = list(map(int,input().split()))
left=0
right=n-1
if a[0] != a[1]:
print(a[0])
elif a[n-1] != a[n-2]:
print(a[n-1])
else:
while left <= right:
mid = ((right-left)//2)+left
pre = mid-1
nxt = mid+1
if (a[pre] != a[mid]) and (a[nxt] != a[mid]):
print(a[mid])
break
elif mid%2==0 :
if a[pre] == a[mid] :
right = mid - 1
else :
left = mid + 1
else :
if a[pre] == a[mid] :
left = mid + 1
else :
right = mid - 1;
Input :
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains an integer n denoting the size of the array. The next line contains n space separated integers forming the array. The last line contains the sum.
Output :
Count all the subsets of given array with sum equal to given sum.
NOTE: Since result can be very large, print the value modulo 109+7.
Constraints :
1<=T<=100
1<=n<=103
1<=a[i]<=103
1<=sum<=103
Example :
Input :
2
6
2 3 5 6 8 10
10
5
1 2 3 4 5
10
Output :
3
3
Explanation :
Testcase 1: possible subsets : (2,3,5) , (2,8) and (10)
Testcase 2: possible subsets : (1,2,3,4) , (2,3,5) and (1,4,5)
Solutions:
C++
#include <bits/stdc++.h>
using namespace std;
void printBool(int n, int len)
{
while (n) {
if (n & 1)
cout << 1;
else
cout << 0;
n >>= 1;
len--;
}
while (len) {
cout << 0;
len--;
}
cout << endl;
}
void printSubsetsCount(int set[], int n, int val)
{
int sum;
int count = 0;
for (int i = 0; i < (1 << n); i++) {
sum = 0;
for (int j = 0; j < n; j++)
if ((i & (1 << j)) > 0) {
sum += set[j];
}
if (sum == val) {
count++;
}
}
if (count == 0) {
cout << ("No subset is found") << endl;
}
else {
cout << count << endl;
}
}
int main()
{
int t,n,sum;
cin>>t;
while(t--)
{
cin>>n;
int set[n];
for(int i=0;i<n;i++)
cin>>set[i];
cin>>sum;
printSubsetsCount(set, n, sum);
}
}
JAVA
import java.io.*;
import java.util.*;
class Main {
static void printBool(int n, int len)
{
while (n>0) {
if ((n & 1) == 1)
System.out.print(1);
else
System.out.print(0);
n >>= 1;
len--;
}
while (len>0) {
System.out.print(0);
len--;
}
System.out.println();
}
static void printSubsetsCount(int set[], int n, int val)
{
int sum;
int count = 0;
for (int i = 0; i < (1 << n); i++) {
sum = 0;
for (int j = 0; j < n; j++)
if ((i & (1 << j)) > 0) {
sum += set[j];
}
if (sum == val) {
count++;
}
}
if (count == 0) {
System.out.println("No subset is found");
}
else {
System.out.println(count);
}
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
int n,sum;
while(t>0)
{
n=sc.nextInt();
int set[] = new int[n];
for(int i=0;i<n;i++)
set[i] = sc.nextInt();
sum = sc.nextInt();
printSubsetsCount(set, n, sum);
t--;
}
}
}
PYTHON
def printBool(n, len):
while n:
if n & 1:
print("1 ")
else:
print("0 ")
n = n >> 1
len -= 1
while len:
print("0 ")
len -= 1
print()
def printSubsetsCount(set, n, val):
sum = 0
count = 0
for i in range(0, 1 << n):
sum = 0
for j in range(0, n):
if (i & 1 << j) > 0:
sum += set[j]
if (sum == val):
count += 1
if (count == 0):
print("No subset is found")
else:
print(count)
t=int(input())
set = []
while t>0:
n = int(input())
set = list((map(int,input().strip().split())))[:n]
Sum = int(input())
printSubsetsCount(set, n, Sum)
t = t-1
Input Format :
The first line contains the number of test cases T, T lines follow.
Each line then contains an integer N, the total number of people attended that meeting.
Output Format :
Print the number of handshakes for each test-case in a new line.
Constraints :
1 <= T <= 1000
0 < N < 106
Sample Input :
2
1
2
Output :
0
1
Explanation :
Case 1 : The lonely board member shakes no hands, hence 0.
Case 2 : There are 2 board members, 1 handshake takes place.
Solutions:
C Language
#include <stdio.h>
int main()
{
int t,n; scanf("%d",&t);
long int sum = 0;
while(t--){
scanf("%d",&n);
n--;
sum = (n*(n+1))/2;
printf("%ld\n",sum);
}
return 0;
}
C++
#include <iostream>
using namespace std;
int main()
{
int t,n,sum; cin >> t;
long long sum;
while(t--){
cin >> n;
n--;
sum = (n*(n+1))/2;
cout << sum << endl ;
}
return 0;
}
JAVA
import java.util.*;
public class Main
{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t,n;
long sum;
t = sc.nextInt();
while(t > 0){
n = sc.nextInt();
n--;
sum = (n*(n+1))/2;
System.out.println(sum);
t--;
}
}
}
PYTHON
t = int(input())
while t > 0 :
n = int(input())
n = n-1;
print((n*(n+1))//2)
t = t-1
If they have 4 books and students, the possible exchanges are 9. Bi is the book of i-th student and after the exchange, he should get a different book, other than Bi.
B1 B2 B3 B4 – first state, before exchange of the books
B2 B1 B4 B3
B2 B3 B4 B1
B2 B4 B1 B3
B3 B1 B4 B2
B3 B4 B1 B2
B3 B4 B2 B1
B4 B1 B2 B3
B4 B3 B1 B2
B4 B3 B2 B1
Find the number of possible exchanges, if the books are exchanged so that every student will receive a different book.
Constraints
1<= N <= 1000000
Input Format
Input contains one line with N, indicates the number of books and number of students.
Output Format
Output the answer modulo 100000007.
Refer the sample output for formatting
Sample Input :
4
Sample Output :
9
Solutions:
C Language
#include <stdio.h>
int main()
{
int mod = (int)1e7+7;
long int n,a=0,b=1,c=2,d,i;
scanf("%ld",&n);
if(n==1 || n==2)
printf("%ld",n-1);
else{
for(i=3 ; i<=n ; i++){
d = (c * (a + b)) % mod ;
a = b;
b = d;
c++;
}
printf("%ld",d);
}
return 0;
}
C++
#include <iostream>
using namespace std;
int main()
{
int mod = (int)1e7+7;
long int n,a=0,b=1,c=2,d,i;
cin >> n;
if(n==1 || n==2)
cout << (n-1);
else{
for(i=3 ; i<=n ; i++){
d = (c * (a + b)) % mod ;
a = b;
b = d;
c++;
}
cout << d;
}
return 0;
}
JAVA
import java.util.*;
public class Main
{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int mod = (int)1e8+7;
long n,a=0,b=1,c=2,d=0;
n = sc.nextLong();
if(n==1 || n==2)
System.out.println(n-1);
else{
for(int i=3 ; i<=n ; i++){
d = (c * (a + b)) % mod ;
a = b;
b = d;
c++;
}
System.out.println(d);
}
}
}
PYTHON
mod = 100000007;
a=0
b=1
c=2
d=0
n = int(input())
if n==1 or n==2:
print(n-1)
else :
for i in range(1,n) :
d = (c * (a + b)) % mod
a = b
b = d
c = c + 1
print(d)
Solutions:
C++
#include <bits/stdc++.h>
using namespace std;
void countSubstring(string s)
{
int res = 0;
for (int i = 0;
i < s.length(); i++) {
int x = 0;
for (int j = i;
j < s.length(); j++) {
int temp = 1 << s[j] - 'a';
x ^= temp;
if ((x & (x - 1)) == 0)
res++;
}
}
cout << res;
}
int main()
{
string str;
getline(cin,str);
countSubstring(str);
return 0;
}
JAVA
import java.util.*;
class Main{
static void countSubString(String s)
{
int res = 0;
for (int i = 0; i < s.length(); i++)
{
int x = 0;
for (int j = i; j < s.length(); j++)
{
int temp = 1 << s.charAt(j) - 'a';
x ^= temp;
if ((x & (x - 1)) == 0)
res++;
}
}
System.out.print(res);
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
countSubString(str);
}
}
PYTHON
def countSubString(s):
res = 0;
for i in range(len(s)):
x = 0;
for j in range(i, len(s)):
temp = 1 << ord(s[j]) - ord('a');
x ^= temp;
if ((x & (x - 1)) == 0):
res += 1;
print(res);
if __name__ == '__main__':
str = input();
countSubString(str);
Problem Statement:
You are given a binary tree with N
nodes where each node contains a positive integer value. The goal is to find the maximum sum path from the root to any leaf node. However, you need to ensure that the sum of the values along the path is not divisible by a given integer K
.
Input:
N
, the number of nodes in the tree.N
space-separated integers representing the values of the nodes.N-1
pairs of integers u
and v
, representing the edges of the tree (the tree is rooted at node 1).K
, the divisor.Output:
K
. If no such path exists, print -1
.
Input:
7 3 4 8 2 1 6 10 1 2 1 3 2 4 2 5 3 6 3 7 5
Output:
21
Explanation:
The possible paths from the root (node 1) to the leaves are:
The path with the maximum sum that is not divisible by 5 is 3 -> 8 -> 10
, with a sum of 21.
Notes:
N
can be as large as 100,000
.Solutions:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> values;
vector<vector<int>> adj;
int K;
int maxSum = -1;
void dfs(int node, int parent, int currentSum) {
currentSum += values[node - 1];
bool isLeaf = true;
for (int neighbor : adj[node]) {
if (neighbor != parent) {
isLeaf = false;
dfs(neighbor, node, currentSum);
}
}
if (isLeaf && currentSum % K != 0) {
maxSum = max(maxSum, currentSum);
}
}
int main() {
int N;
cin >> N;
values.resize(N);
adj.resize(N + 1);
for (int i = 0; i < N; i++) {
cin >> values[i];
}
for (int i = 0; i < N - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
cin >> K;
dfs(1, -1, 0);
cout << maxSum << endl;
return 0;
}
import java.util.*;
public class Main {
static List<Integer>[] adj;
static int[] values;
static int K;
static int maxSum = -1;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
values = new int[N];
adj = new ArrayList[N + 1];
for (int i = 0; i < N; i++) {
values[i] = sc.nextInt();
}
for (int i = 1; i <= N; i++) {
adj[i] = new ArrayList<>();
}
for (int i = 0; i < N - 1; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
adj[u].add(v);
adj[v].add(u);
}
K = sc.nextInt();
dfs(1, -1, 0);
System.out.println(maxSum);
}
static void dfs(int node, int parent, int currentSum) {
currentSum += values[node - 1];
boolean isLeaf = true;
for (int neighbor : adj[node]) {
if (neighbor != parent) {
isLeaf = false;
dfs(neighbor, node, currentSum);
}
}
if (isLeaf && currentSum % K != 0) {
maxSum = Math.max(maxSum, currentSum);
}
}
}
def dfs(node, parent, current_sum):
global max_sum
current_sum += values[node - 1]
is_leaf = True
for neighbor in adj[node]:
if neighbor != parent:
is_leaf = False
dfs(neighbor, node, current_sum)
if is_leaf and current_sum % K != 0:
max_sum = max(max_sum, current_sum)
N = int(input())
values = list(map(int, input().split()))
adj = {i: [] for i in range(1, N + 1)}
for _ in range(N - 1):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)
K = int(input())
max_sum = -1
dfs(1, -1, 0)
print(max_sum)
K
, it is compared to the current maximum sum, and the maximum is updated if necessary.-1
.
TCS NQT Verbal Ability Questions |
TCS NQT Coding Questions |