Warm-up Challenges
1. Sock Merchant (Python 2)
#!/bin/python
import math
import os
import random
import re
import sys
def sockMerchant(n, ar):
count = 0
ar.sort()
ar.append('#')
i = 0
while i<n:
if ar[i]==ar[i+1]:
count = count+1
i+=2
else:
i+=1
return count
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n = int(raw_input())
ar = map(int, raw_input().rstrip().split())
result = sockMerchant(n, ar)
fptr.write(str(result) + '\n')
fptr.close()
import math
import os
import random
import re
import sys
def sockMerchant(n, ar):
count = 0
ar.sort()
ar.append('#')
i = 0
while i<n:
if ar[i]==ar[i+1]:
count = count+1
i+=2
else:
i+=1
return count
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n = int(raw_input())
ar = map(int, raw_input().rstrip().split())
result = sockMerchant(n, ar)
fptr.write(str(result) + '\n')
fptr.close()
2. Counting Valleys (Python 2)
#!/bin/python
import math
import os
import random
import re
import sys
# Complete the countingValleys function below.
def countingValleys(n, s):
level=valley=0
for i in range(n):
if(s[i]=='U'):
level+=1
if(level==0):
valley+=1
else:
level-=1
return valley
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n = int(raw_input())
s = raw_input()
result = countingValleys(n, s)
fptr.write(str(result) + '\n')
fptr.close()
import math
import os
import random
import re
import sys
# Complete the countingValleys function below.
def countingValleys(n, s):
level=valley=0
for i in range(n):
if(s[i]=='U'):
level+=1
if(level==0):
valley+=1
else:
level-=1
return valley
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n = int(raw_input())
s = raw_input()
result = countingValleys(n, s)
fptr.write(str(result) + '\n')
fptr.close()
3. Jumping on the Clouds (javascript node.js)
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.replace(/\s*$/, '')
.split('\n')
.map(str => str.replace(/\s*$/, ''));
main();
});
function readLine() {
return inputString[currentLine++];
}
// Complete the jumpingOnClouds function below.
function jumpingOnClouds(c) {
var jumpCount = 0;
let step = 0;
for(let i=0; i<c.length; i){
if(c[i] === 0 && i !== (c.length - 2)){
i = i + 2;
jumpCount++
} else if (c[i] === 0 && i === (c.length - 2)){
i = i + 1;
jumpCount++
} else {
i = i - 1;
}
}
return jumpCount - 1;
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const n = parseInt(readLine(), 10);
const c = readLine().split(' ').map(cTemp => parseInt(cTemp, 10));
let result = jumpingOnClouds(c);
ws.write(result + "\n");
ws.end();
}
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.replace(/\s*$/, '')
.split('\n')
.map(str => str.replace(/\s*$/, ''));
main();
});
function readLine() {
return inputString[currentLine++];
}
// Complete the jumpingOnClouds function below.
function jumpingOnClouds(c) {
var jumpCount = 0;
let step = 0;
for(let i=0; i<c.length; i){
if(c[i] === 0 && i !== (c.length - 2)){
i = i + 2;
jumpCount++
} else if (c[i] === 0 && i === (c.length - 2)){
i = i + 1;
jumpCount++
} else {
i = i - 1;
}
}
return jumpCount - 1;
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const n = parseInt(readLine(), 10);
const c = readLine().split(' ').map(cTemp => parseInt(cTemp, 10));
let result = jumpingOnClouds(c);
ws.write(result + "\n");
ws.end();
}
4. Repeated String (PHP)
<?php
// Complete the repeatedString function below.
function repeatedString($s, $n) {
for ($i = 0;$i<strlen($s);$i++) if ($s[$i] == 'a') $cnt++;
$p = floor($n / strlen($s));
$p *= $cnt;
if ($n%strlen($s)) {
$r = $n % strlen($s);
for ($i = 0; $i < $r; $i++) if ($s[$i] == 'a') $p++;
}
return $p;
}
$fptr = fopen(getenv("OUTPUT_PATH"), "w");
$stdin = fopen("php://stdin", "r");
$s = '';
fscanf($stdin, "%[^\n]", $s);
fscanf($stdin, "%ld\n", $n);
$result = repeatedString($s, $n);
fwrite($fptr, $result . "\n");
fclose($stdin);
fclose($fptr);
// Complete the repeatedString function below.
function repeatedString($s, $n) {
for ($i = 0;$i<strlen($s);$i++) if ($s[$i] == 'a') $cnt++;
$p = floor($n / strlen($s));
$p *= $cnt;
if ($n%strlen($s)) {
$r = $n % strlen($s);
for ($i = 0; $i < $r; $i++) if ($s[$i] == 'a') $p++;
}
return $p;
}
$fptr = fopen(getenv("OUTPUT_PATH"), "w");
$stdin = fopen("php://stdin", "r");
$s = '';
fscanf($stdin, "%[^\n]", $s);
fscanf($stdin, "%ld\n", $n);
$result = repeatedString($s, $n);
fwrite($fptr, $result . "\n");
fclose($stdin);
fclose($fptr);
5. 2D Array - DS (JAVA 7)
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class Solution {
// Complete the hourglassSum function below.
static int hourglassSum(int[][] arr) {
int sum=-1000;
for(int i =0 ; i<4;i++){
for(int x =0 ; x<4; x++){
int top = arr[i][x]+arr[i][x+1]+arr[i][x+2];
int middle = arr[i+1][x+1];
int bottom = arr[i+2][x]+arr[i+2][x+1]+arr[i+2][x+2];
if(top+middle+bottom>sum){sum=top+middle+bottom;}
}
}
return sum;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int[][] arr = new int[6][6];
for (int i = 0; i < 6; i++) {
String[] arrRowItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int j = 0; j < 6; j++) {
int arrItem = Integer.parseInt(arrRowItems[j]);
arr[i][j] = arrItem;
}
}
int result = hourglassSum(arr);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedWriter.close();
scanner.close();
}
}
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class Solution {
// Complete the hourglassSum function below.
static int hourglassSum(int[][] arr) {
int sum=-1000;
for(int i =0 ; i<4;i++){
for(int x =0 ; x<4; x++){
int top = arr[i][x]+arr[i][x+1]+arr[i][x+2];
int middle = arr[i+1][x+1];
int bottom = arr[i+2][x]+arr[i+2][x+1]+arr[i+2][x+2];
if(top+middle+bottom>sum){sum=top+middle+bottom;}
}
}
return sum;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int[][] arr = new int[6][6];
for (int i = 0; i < 6; i++) {
String[] arrRowItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int j = 0; j < 6; j++) {
int arrItem = Integer.parseInt(arrRowItems[j]);
arr[i][j] = arrItem;
}
}
int result = hourglassSum(arr);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedWriter.close();
scanner.close();
}
}
6. Arrays: Left Rotation (Python 2)
#!/bin/python
import math
import os
import random
import re
import sys
# Complete the rotLeft function below.
def rotLeft(a, d):
return a[d:] + a[:d]
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
nd = raw_input().split()
n = int(nd[0])
d = int(nd[1])
a = map(int, raw_input().rstrip().split())
result = rotLeft(a, d)
fptr.write(' '.join(map(str, result)))
fptr.write('\n')
fptr.close()
import math
import os
import random
import re
import sys
# Complete the rotLeft function below.
def rotLeft(a, d):
return a[d:] + a[:d]
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
nd = raw_input().split()
n = int(nd[0])
d = int(nd[1])
a = map(int, raw_input().rstrip().split())
result = rotLeft(a, d)
fptr.write(' '.join(map(str, result)))
fptr.write('\n')
fptr.close()
7. New Year Chaos (SCALA)
/*
https://www.hackerrank.com/challenges/new-year-chaos
*/
object Solution {
// Binary Index Tree (aka. Fenwick tree), storing how many times `>=i` occurs.
//
// Most examples of BIT store the SUM of elements for indeces up to `i`.
// Instead, this implementation is designed to store and query the COUNT of
// elements for indeces from `i` and above.
case class BITree(n: Int) {
private val a = new Array[Int](n)
def add(i: Int): Unit =
for {x <- Iterator.iterate(i+1) { j => j - (j & -j) }.takeWhile(_ > 0)}
a(x-1) += 1
def count(i: Int): Int = ( // [i,n]
for {x <- Iterator.iterate(i+1) { j => j + (j & -j) }.takeWhile(_ <= n)}
yield a(x-1)
).sum
}
def minBribes(n: Int, input: Iterator[Int]): Int = {
val bit = BITree(n)
input.zipWithIndex.foldLeft(0) {
case (acc, (i, index)) if acc < 0 || i-2 > index+1 => -1
case (acc, (i, index)) =>
bit.add(i-1)
acc + bit.count(i)
}
}
def main(args: Array[String]) {
val scanner = new java.util.Scanner(System.in)
for {_ <- 0 until scanner.nextInt} {
val n = scanner.nextInt
minBribes(n, Iterator.fill(n) { scanner.nextInt }) match {
case -1 => println("Too chaotic")
case x => println(x)
}
}
}
}
https://www.hackerrank.com/challenges/new-year-chaos
*/
object Solution {
// Binary Index Tree (aka. Fenwick tree), storing how many times `>=i` occurs.
//
// Most examples of BIT store the SUM of elements for indeces up to `i`.
// Instead, this implementation is designed to store and query the COUNT of
// elements for indeces from `i` and above.
case class BITree(n: Int) {
private val a = new Array[Int](n)
def add(i: Int): Unit =
for {x <- Iterator.iterate(i+1) { j => j - (j & -j) }.takeWhile(_ > 0)}
a(x-1) += 1
def count(i: Int): Int = ( // [i,n]
for {x <- Iterator.iterate(i+1) { j => j + (j & -j) }.takeWhile(_ <= n)}
yield a(x-1)
).sum
}
def minBribes(n: Int, input: Iterator[Int]): Int = {
val bit = BITree(n)
input.zipWithIndex.foldLeft(0) {
case (acc, (i, index)) if acc < 0 || i-2 > index+1 => -1
case (acc, (i, index)) =>
bit.add(i-1)
acc + bit.count(i)
}
}
def main(args: Array[String]) {
val scanner = new java.util.Scanner(System.in)
for {_ <- 0 until scanner.nextInt} {
val n = scanner.nextInt
minBribes(n, Iterator.fill(n) { scanner.nextInt }) match {
case -1 => println("Too chaotic")
case x => println(x)
}
}
}
}
8. Minimum Swaps 2 (JAVA 8)
import java.util.Map;
import java.util.Scanner;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Solution {
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 < arr.length; i++) {
arr[i] = sc.nextInt();
}
System.out.println(solve(arr));
sc.close();
}
static int solve(int[] arr) {
Map<Integer, Integer> numberToIndex = IntStream.range(0, arr.length).boxed()
.collect(Collectors.toMap(i -> arr[i], Function.identity()));
int swapNum = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] != i + 1) {
int otherIndex = numberToIndex.get(i + 1);
numberToIndex.put(arr[i], otherIndex);
numberToIndex.put(i + 1, i);
swap(arr, i, otherIndex);
swapNum++;
}
}
return swapNum;
}
static void swap(int[] arr, int index1, int index2) {
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
}
import java.util.Scanner;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Solution {
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 < arr.length; i++) {
arr[i] = sc.nextInt();
}
System.out.println(solve(arr));
sc.close();
}
static int solve(int[] arr) {
Map<Integer, Integer> numberToIndex = IntStream.range(0, arr.length).boxed()
.collect(Collectors.toMap(i -> arr[i], Function.identity()));
int swapNum = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] != i + 1) {
int otherIndex = numberToIndex.get(i + 1);
numberToIndex.put(arr[i], otherIndex);
numberToIndex.put(i + 1, i);
swap(arr, i, otherIndex);
swapNum++;
}
}
return swapNum;
}
static void swap(int[] arr, int index1, int index2) {
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
}
9. Array Manipulation (JAVA 8)
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class Solution {
// Complete the arrayManipulation function below.
static long arrayManipulation(int n, int[][] queries) {
long[] computation = new long[n];
for (int i = 0; i < queries.length; i++) {
int a = queries[i][0] - 1;
int b = queries[i][1] - 1;
int k = queries[i][2];
computation[a] += k;
if (b + 1 < n ) {
computation[b + 1] -= k;
}
}
long max = 0; long sum = 0;
for (int i = 0; i < n; i++) {
sum += computation[i];
max = Math.max(max, sum);
}
return max;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String[] nm = scanner.nextLine().split(" ");
int n = Integer.parseInt(nm[0]);
int m = Integer.parseInt(nm[1]);
int[][] queries = new int[m][3];
for (int i = 0; i < m; i++) {
String[] queriesRowItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int j = 0; j < 3; j++) {
int queriesItem = Integer.parseInt(queriesRowItems[j]);
queries[i][j] = queriesItem;
}
}
long result = arrayManipulation(n, queries);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedWriter.close();
scanner.close();
}
}
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class Solution {
// Complete the arrayManipulation function below.
static long arrayManipulation(int n, int[][] queries) {
long[] computation = new long[n];
for (int i = 0; i < queries.length; i++) {
int a = queries[i][0] - 1;
int b = queries[i][1] - 1;
int k = queries[i][2];
computation[a] += k;
if (b + 1 < n ) {
computation[b + 1] -= k;
}
}
long max = 0; long sum = 0;
for (int i = 0; i < n; i++) {
sum += computation[i];
max = Math.max(max, sum);
}
return max;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String[] nm = scanner.nextLine().split(" ");
int n = Integer.parseInt(nm[0]);
int m = Integer.parseInt(nm[1]);
int[][] queries = new int[m][3];
for (int i = 0; i < m; i++) {
String[] queriesRowItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int j = 0; j < 3; j++) {
int queriesItem = Integer.parseInt(queriesRowItems[j]);
queries[i][j] = queriesItem;
}
}
long result = arrayManipulation(n, queries);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedWriter.close();
scanner.close();
}
}
